Re:P vs. NP: An Assumption That Runs the Internet
by mdxn on Sunday November 29, 2015 @02:14PM
(#10645651)
The actual decision problem statement for TSP is "Does there exist a tour of less than length L".
It is easy to prove if such a tour exists: simply give me tour. I can sum up the lengths and check that the sum < L. Finding such a tour is the computationally hard part in the worst of cases.
It is easy to prove if such a tour exists: simply give me tour. I can sum up the lengths and check that the sum < L. Finding such a tour is the computationally hard part in the worst of cases.