News for hackers. Stuff that matters.
Re:The never-ending finite loop by SamReidHughes on Tuesday August 03, 2010 @04:31AM (#1570513)
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.

There are no comments on this comment yet.