Re:The never-ending finite loop
by swolchok on Monday August 02, 2010 @11:53PM
(#1570062)
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.
[ Parent
| on HN ]
There are no comments on this comment yet.