7
$\begingroup$

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.

$\endgroup$
7
  • 2
    $\begingroup$ The example in Wikipedia actually works for any problem in NP. $\endgroup$ Apr 5, 2020 at 18:45
  • 1
    $\begingroup$ @YuvalFilmus Ah, I did not know that. Any algorithm specifically designed for a specific problem? $\endgroup$
    – DUO Labs
    Apr 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$
    – Laakeri
    Apr 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$
    – ComFreek
    Apr 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$ Apr 9, 2020 at 18:10

1 Answer 1

7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.