News for hackers. Stuff that matters.
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.
Re:The never-ending finite loop by bdr on Monday August 02, 2010 @02:18PM (#1568484)
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.
Re:The never-ending finite loop by sukuriant on Monday August 02, 2010 @03:50PM (#1568801)
As a side note, you're partly assuming in that statement that P != NP, which is yet to be determined in either direction.
Re:The never-ending finite loop by sqrt17 on Monday August 02, 2010 @05:37PM (#1569177)
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.
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.