Re:The never-ending finite loop
by nollidge on Monday August 02, 2010 @12:27PM
(#1568068)
As someone points out in the comments, isn't this true of any NP-complete problem with large enough inputs? This isn't all that surprising then.
[ Parent
| on HN ]
You can write a finite-but-longer-than-the-universe loop using any non-constant problem with large enough inputs. There are classes harder than NP, so NP-completeness is not particularly relevant.
As a side note, you're partly assuming in that statement that P != NP, which is yet to be determined in either direction.
He's not. 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.
If you want an analogy: sorting an array is clearly a task that can be solved in O(n log n) time, but if you write a bubble sort implementation (or any other O(n^2) algorithm), the program will still take O(n^2) time.
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.Right conclusion, not the most direct argument. NP is a proper subset of EXPTIME; there are problems that must take exponential time to complete. Wikipedia says that asking whether a Turing-machine halts in k steps is EXPTIME-complete (you have to execute k steps and the input is of size log k), but if you're willing to fudge a bit and consider function problems, listing all paths in a graph (or something even simpler, like "list all n-bit binary numbers")is going to take exponential time in the worst case.