3 ms·
That 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 differen
by Armisael16 5y ago
That 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.