HiveBrain v1.2.0
Get Started
← Back to all entries
principleMinor

Algorithms that run in polynomial time if P=NP

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
polynomialtimealgorithmsthatrun

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#123665, answer score: 7

Revisions (0)

No revisions yet.