2 ms·
Any program code written today that solves an NP-hard problem without exploiting special properties of the input data will take exponential time. If we discover
by SamReidHughes 16y ago
Any program code written today that solves an NP-hard problem without exploiting special properties of the input data will take exponential time. If we discover a smart way to do NP-hard problems in polynomial time, we'll have a better solution for the problem, but the old program code will stay the same.
You could write a program that runs in polynomial time, but be unable to prove that it does. Then, later, you could find a proof that the program runs in polynomial time. In fact, if P=NP, you can write such a program right now:
for each string s in the enumeration of all strings {
if (s = p + q where
(p is a program and
q is a proof that p solves 3SAT in polynomial time)) {
run p on the input;
return;
}
}
Also, you could interleave the execution of this program with one that solves 3SAT in exponential time. Then you'll have a program that works in any case, and that solves 3SAT in polynomial time if P = NP.