3 ms·

> Do you not realize that P vs. NP might have a negative outcome (extremely likely) The outcome will matter less than having an answer. And I do think it will

by js8 3y ago

> Do you not realize that P vs. NP might have a negative outcome (extremely likely) The outcome will matter less than having an answer. And I do think it will be a negative outcome either way, because it will obsolete lot of beautiful math, and replace it with a more mechanical process. > In basically any field proving the existence of a solution is far, far harder than calculating the solution numerically. First of all, if you want to ascertain whether the numerical algorithm works correctly, you have to prove the existence of the solution. That's part of the (equation -> solution algorithm) conversion process. Now, you can possibly get by without proving existence of the solution for the infinite family (and confront the numerical solution directly with reality). But doing that is more complicated than, assuming there is a SAT solver, plug the SAT instance into it and see if there is a solution (and you can get, for a finite family of instances, a similar guarantee you would get from the existence proof). > Not even the assumption is right. Not sure what assumption you refer to. Computers don't run algorithms (because algorithms handle unbounded input/output), computers are just a very large state machines. So you need to convert the algorithm to a state machine first. Saying "run algorithm on a computer" is just a useful figure of speech, but somewhat misleading, because it implies certain quantization.

constantcrying 3y ago
>The outcome will matter less than having an answer. And I do think it will be a negative outcome either way, because it will obsolete lot of beautiful math, and replace it with a more mechanical process. The negative outcome will have exactly zero implications about anything. Except "turns out we were right all along" polynomial problems are just fundamentally less hard than problems you can verify the solution of in polynomial time. This has ZERO implications on anyone, except the mathematicians who prove it, who will get a price and quite a bit of academic fame. That is literally it. >But doing that is more complicated than, assuming there is a SAT solver, plug the SAT instance into it and see if there is a solution (and you can get, for a finite family of instances, a similar guarantee you would get from the existence proof). Even is SAT is P that doesn't imply a solution can feasibly be found. And if P neq NP, then SAT might not be P.
- js8 3y ago
  > Even is SAT is P that doesn't imply a solution can feasibly be found. It does, because in this case you also assumed that running numerical algorithm was feasible. So if your SAT solver fails to find the answer, it is either suboptimal method (because numerical method exists), or (if the instance is UNSAT) the numerical method gives you a flawed result.
  - constantcrying 3y ago
    Do you not understand that an O(n^100) algorithm is in P, but can never be run feasibly on a computer for any non trivial amounts of n? For n=10 you are already far beyond the number of Atoms in the universe. I don't think you have any clue what you are actually talking about.
- Tainnor 3y ago
  > And if P neq NP, then SAT might not be P. Small correction: If P != NP, then SAT definitely isn't in P. That's because SAT is NP-complete, so if it was in P, every other NP problem could be polynomially reduced to it and would hence also be in P.

by js8 3y ago

constantcrying 3y ago

>The outcome will matter less than having an answer. And I do think it will be a negative outcome either way, because it will obsolete lot of beautiful math, and replace it with a more mechanical process. The negative outcome will have exactly zero implications about anything. Except "turns out we were right all along" polynomial problems are just fundamentally less hard than problems you can verify the solution of in polynomial time. This has ZERO implications on anyone, except the mathematicians who prove it, who will get a price and quite a bit of academic fame. That is literally it. >But doing that is more complicated than, assuming there is a SAT solver, plug the SAT instance into it and see if there is a solution (and you can get, for a finite family of instances, a similar guarantee you would get from the existence proof). Even is SAT is P that doesn't imply a solution can feasibly be found. And if P neq NP, then SAT might not be P.

js8 3y ago
> Even is SAT is P that doesn't imply a solution can feasibly be found. It does, because in this case you also assumed that running numerical algorithm was feasible. So if your SAT solver fails to find the answer, it is either suboptimal method (because numerical method exists), or (if the instance is UNSAT) the numerical method gives you a flawed result.
- constantcrying 3y ago
  Do you not understand that an O(n^100) algorithm is in P, but can never be run feasibly on a computer for any non trivial amounts of n? For n=10 you are already far beyond the number of Atoms in the universe. I don't think you have any clue what you are actually talking about.
Tainnor 3y ago
> And if P neq NP, then SAT might not be P. Small correction: If P != NP, then SAT definitely isn't in P. That's because SAT is NP-complete, so if it was in P, every other NP problem could be polynomially reduced to it and would hence also be in P.