0
$\begingroup$

If P=NP (polynomial time algorithm for determining whether there exists a route smaller than L) would the NP-Hard version of TSP (finding the minimum distance route) still be NP-Hard? We would only need to find the upper (b) and lower bounds (a) and optimise (assuming discrete distances this should still stay polynomially bounded*). Is this correct?

*the number of times we would have to run the polynomial time algorithm should be $\log_{2}(b-a)$ which means it still stays in P

$\endgroup$
3
  • $\begingroup$ A bit of nitpickery: you should specify the precise question you're asking, in particular for purposes of talking about NP vs. FNP (i.e., is your output a yes/no question or a number?). In any case, you're correct for essentially the reasons you state — in fact, for the decision version ('is $\ell$ the length of a shortest path?') you can do it with just two queries ('is there a path of length $\leq\ell$?', 'is there a path of length $\leq\ell-1$?') both of which are (under your hypothesis) in P. $\endgroup$ Commented Apr 6 at 17:10
  • $\begingroup$ @StevenStadnicki My point is (probably wasn't very clear) I thought P=NP should most probably not have any consequences on NP-hard. But this clearly indicates that at least for this problem the NP-hard version (optimisation version) should also be P. I'm quite inexperienced in the subject so forgive my imprecision. $\endgroup$
    – David
    Commented Apr 6 at 17:19
  • $\begingroup$ As NP-hard problems go, this is a 'simple' one; P=NP is actually known to have dramatic consequences on harder problems. In particular, the polynomial hierarchy collapses. $\endgroup$ Commented Apr 6 at 18:10

1 Answer 1

3
$\begingroup$

If P=NP, NP-hard problems are still NP-hard, but in that situation, NP-hard doesn't mean that the problem is necessarily hard.

If P=NP, the optimization version of TSP (finding the minimum distance route) can be solved in polynomial time, e.g., by using an algorithm to solve the decision problem multiple times (plus binary search or other methods to reconstruct a specific solution).

$\endgroup$
5
  • $\begingroup$ Is it obvious that the sum-of-square-roots issue goes away if P=NP? (Could be an issue for Euclidean TSP?) $\endgroup$
    – Neal Young
    Commented Apr 7 at 2:40
  • $\begingroup$ @NealYoung It's not, but the catch there is that Euclidean TSP isn't known to be in NP, because we don't know that a solution can be verified in polynomial time, so it doesn't really factor into the discussion at all. $\endgroup$ Commented Apr 7 at 4:58
  • $\begingroup$ @NealYoung The question asks about the Traveling salesman problem, not Euclidean TSP (where the problem instance is presented by providing the coordinates of the cities). To my knowledge, there is no sum-of-square-roots issue with the TSP. I believe what I wrote is correct. $\endgroup$
    – D.W.
    Commented Apr 8 at 17:14
  • $\begingroup$ Yes, I agree your answer is correct. The intention of my comment was not clear: I am just wondering (only tangentially related to your answer) if the sum-of-square-roots issue goes away if P=NP... $\endgroup$
    – Neal Young
    Commented Apr 8 at 22:43
  • $\begingroup$ @NealYoung, oh, fascinating question! Sounds worth asking separately (maybe on CSTheory.SE?) to see if anything is known, maybe...? $\endgroup$
    – D.W.
    Commented Apr 9 at 0:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.