3 ms·
I 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
by tylerhou 5y ago
I 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.