4 ms·
Technically, if P=NP then we already have a working algorithm to solve NP problems in polynomial time. It involves iterating through and running all possible p
by murbard2 9y ago
Technically, if P=NP then we already have a working algorithm to solve NP problems in polynomial time.
It involves iterating through and running all possible programs ordered by length, giving them an increasing amount of time to run and checking (in polynomial time) if they produce the correct answer.
If there exists a program that finds the answer in polynomial time, this algorithm will eventually find it after wasting (at most polynomial) time iterating through other programs and tentative bounds.
If P != NP, it's still at least asymptotically optimal.
- sdenton4 9y agoHmm, but running 'all possible programs' is an exponential time operation (in the lengths of the programs)...
- murbard2 9y agoYes, but as you note, "in the size of the program" and the size of {the program that solves 3-SAT in polynomial time if there is one} is a constant, so it's all constant. Of course, that constant is astronomically unpractical.
- ufo 9y agoI like the term "Galactic Algorithm" for these algorithms with unpractical constants. https://rjlipton.wordpress.com/2010/10/23/galactic-algorithms/ https://rjlipton.wordpress.com/2010/10/23/galactic-algorithm...
- Tloewald 9y agoPolynomial time is unbounded. Indeed constant Time is unbounded.