3 ms·
Correct me if I am wrong, but I don’t think the decision problem “does an optimal path in TSP have length K” is in NP (as it likely cannot be checked in polynom
by tylerhou 5y ago
Correct me if I am wrong, but I don’t think the decision problem “does an optimal path in TSP have length K” is in NP (as it likely cannot be checked in polynomial time).
Otherwise, we could solve optimal path TSP in polynomial time by binary searching over K.
https://blog.computationalcomplexity.org/2014/01/is-traveling-salesman-np-complete.html?m=1 https://blog.computationalcomplexity.org/2014/01/is-travelin...
- Armisael16 5y agoThat isn’t quite how the decision problem is usually phrased. It’s usually “Is there a path of at most length L?”, which is pretty easily in NP. Minor difference in wording but a big difference in complexity. Asking for the optimal solution of most of the classic NP problems will make them not NP.
- tylerhou 5y agoI was aware of that distinction (of the decision problem), but I didn’t make the connection that solving the canonical decision problem in polynomial time meant that you could also solve the optimization problem in polynomial time with binary search, which is true. But the linked post also claims checking whether a path is optimal is not in NP. Even then, P=NP would still imply TSP could be solved in polynomial time. So I was kinda wrong, for subtle reasons…
- throwaway81523 5y agoAsking whether a given path is optimal is in co-NP. You can prove that the path is non-optimal by exhibiting a shorter path.
- beecafe 5y agoGiven a solution to the decision version of TSP, you can verify whether that solution is valid in polynomial time - just check if it does visit the nodes and is of the claimed length. A normal Turing machine could perform this check in poly time, and a nondeterministic one could check all solutions (exponentially many) in poly time, hence NP.