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).
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).