So if someone proves with an algorithm that SAT can be solved in deterministic polynomial time, then P = NP and that's it?
4
-
2$\begingroup$ en.wikipedia.org/wiki/P_versus_NP_problem#NP-completeness $\endgroup$– D.W. ♦Jul 22, 2022 at 6:58
-
4$\begingroup$ That would be indeed it. Actually, proving that such an algorithm exists would be enough (without giving an algorithm). The only problem is that nobody has the slightest idea how to do this. $\endgroup$– gnasher729Jul 22, 2022 at 8:34
-
$\begingroup$ Just curious... Has anybody tried to publish an effort or something on this? $\endgroup$– just_learningJul 22, 2022 at 9:57
-
3$\begingroup$ @just_learning: there are thousand articles on the topic. $\endgroup$– user16034Jul 22, 2022 at 10:41
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Yes, that would be it – just as if someone had found $a,b,c,n>2$ satisfying $a^n+b^n=c^n$, that would have been it for Fermat's last theorem.
No one ever found such numbers, and the reason turned out to be that there aren't any: the conjecture was true. It seems likely that the reason no one has found a polynomial-time SAT solver after all these decades is also that there aren't any.
There are barriers to proving P=NP. In particular, the famous relativization barrier applies to proofs of P=NP as well as P≠NP. But I don't know whether that implies that a polynomial-time algorithm is hard to find, or just means that any algorithm that you did find would, in fact, not relativize as a proof.
It might also be possible to prove P=NP nonconstructively, i.e., without presenting any particular algorithm. But it's easy to prove that a SAT solver that simulates all Turing machines in parallel until one of them produces a correct answer completes in polynomial time if P=NP, so we would still know a polynomial-time SAT solving algorithm in that case, though it's utterly useless because of the astronomical constant factor.
