On Wikipedia, it says that that there are some algorithms that would run in polynomial time if and only if P=NP. They gave one example (without citation), but are there any others? I tried looking them up and couldn't find any.
$\begingroup$
$\endgroup$
7
-
2$\begingroup$ The example in Wikipedia actually works for any problem in NP. $\endgroup$– Yuval FilmusApr 5, 2020 at 18:45
-
1$\begingroup$ @YuvalFilmus Ah, I did not know that. Any algorithm specifically designed for a specific problem? $\endgroup$– DUO LabsApr 5, 2020 at 18:58
-
1$\begingroup$ I feel like if such algorithm that is not an infinite enumeration of algorithms would be known, then the understanding of P vs NP would be much higher than it currently is. $\endgroup$– LaakeriApr 6, 2020 at 7:27
-
3$\begingroup$ Levin's algorithm given on Wikipedia just accepts in poly-time. It does not run in poly-time overall because it runs forever for words not in SUBET-SUM. $\endgroup$– ComFreekApr 6, 2020 at 8:55
-
1$\begingroup$ See the CSTheory posting, If P=NP, could we obtain proofs of Goldbach's Conjecture etc.?. The answers are quite informative. $\endgroup$– Joseph O'RourkeApr 9, 2020 at 18:10
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
Wikipedia is describing Levin's universal algorithm. This is an algorithm for verifiable problems, which is competitive with the optimal algorithm (in some sense). In particular, the exact same approach would work for any problem in NP, not just SUBSET-SUM.
answered Apr 5, 2020 at 18:46