News for hackers. Stuff that matters.
Re:The TSP Isn't NP Complete by tgflynn on Monday December 30, 2013 @12:47PM (#6985736)
The size of the set k may be exponential but if you have a decision function D(C) == 1 iff there exists a path of cost < C you can use that function to do a binary search over all k's in polynomial time because binary search is log time.

Each call to D should give you 1 bit of the solution and with n bits you can represent numbers from 0 to O(2^n).

There are no comments on this comment yet.