4
$\begingroup$

I have a question concerning several NP-hard problems and why they are (or are not NP-complete).

I understand the concepts behind NP-hard and NP-complete: Problem lies in NPC if it is NP-hard and also in NP (we can verify its solution in polynomial time).

I know that Traveling Salesman (TSP) is NP-hard but isn't NP-complete (NPC), because in order to verify its solution, we would need to check that no better solution exists and hence solve it in polynomial time (so its not in NP).

However, problems like Knapsack or ILP (Integer Linear Programming) are said to be in NPC. Why is that? Isn't there the same analogy as with TSP? If someone gives us a solution and claims it is optimal, we would need to verify that no better solution exists and therefor solve these problems to obtain it in polynomial time.

Why is ILP and Knapsack in NPC and not just NP-hard? I hope my question is not too confusing, I will try to rephrase it if so.

$\endgroup$
13
  • 1
    $\begingroup$ I don't know where you got this difference from? Remember that complexity classes are always decision problems (output is only 0 or 1). For TSP this would be "is there a tour of length smaller than C?" Similar to knapsack and ILP, this is NPC. What decision version of TSP would be NP Hard then? $\endgroup$ Jun 11, 2016 at 7:42
  • $\begingroup$ @AlbertHendriks Yes, that is right. But even the decision version of TSP is not NPC (it is only NP-hard). See this: ibm.com/developerworks/community/blogs/jfp/entry/… $\endgroup$
    – Smajl
    Jun 11, 2016 at 7:44
  • 1
    $\begingroup$ Regarding the article, you could say that problems are NP-hard even if they're not a decision problem. In that sense your version of TSP is NP-Hard and not NP-Complete. They could write the same article about Knapsack and it would also be NP-Hard then. The article is technically correct but confusing. When people say TSP they mean the decision version and that's NPC. Btw your interpetation is wrong: "TSPDECISION : Given a number L, a set of cities, and distance between all city pairs, is there a tour visiting each city exactly once of length less than L? This problem is indeed NP complete" $\endgroup$ Jun 11, 2016 at 7:51
  • $\begingroup$ @AlbertHendriks But i don't understand how the decision version ('There is no shorter ham. circ. than k') of TSP can be NPC? How can you verify that no shorter path exists in polynomial time without actually solving TSP? $\endgroup$
    – Smajl
    Jun 11, 2016 at 7:55
  • $\begingroup$ The decision problem is not about whether there isn't any shorter path. The decision problem is whether there is a path shorter than 10. (L is a given value in the input). $\endgroup$ Jun 11, 2016 at 7:57

1 Answer 1

8
$\begingroup$

As discussed in the comments, this question hinges around subtleties of the definitions. NP is a set of decision problems (problems with yes/no answers), so any problem such as "Find the shortest XXX" is automatically excluded. Natural problems come in a number of variants and it's sometimes important to distinguish between them.

To a complexity theorist, the travelling salesman problem (TSP) is exactly the following problem:

  • Input: An $n\times n$ matrix giving the pairwise distances between $n$ cities, and a target distance $d$.
  • Question: Is it possible to start at one of the cities, visit every other city exactly once and return to the starting city while travelling total distance at most $d$? (Equivalently, does the shortest such route have total length at most $d$?)

Then there is the following optimization problem, MIN-TSP:

  • Input: An $n\times n$ matrix giving the pairwise distances between $n$ cities.
  • Question: What is the shortest distance it is possible to travel in order to start at some city, visit each of the others exactly once and return to the start city?

There are also other variants: F-TSP (function-TSP) has the same input as TSP but the output is a route of length at most $d$, if one exists, and "no", otherwise, rather than just yes or no; F-MIN-TSP is the analogous version of MIN-TSP.

These problems are all inter-related but they're not the same problem. In particular, only TSP is a decision problem: MIN-TSP is an optimization problem and the F- problems are function problems. TSP itself is NP-complete. If you can solve MIN-TSP, you can clearly solve TSP by computing the minimum and comparing it against $d$, so MIN-TSP is NP-hard (but can't be complete because it's not a decision problem so it's not in NP). Conversely, if you can solve TSP and you're allowed to make multiple TSP queries, then you can solve MIN-TSP by binary search.

For the function versions, being able to solve F-TSP clearly allows you to solve TSP: if F-TSP gives you a route, say "yes"; otherwise, say "no". Similarly for F-MIN-TSP. On the other hand, it's not clear that being able to solve TSP helps you solve F-TSP: being told that it's possible to visit the capitals of the 48 contiguous states and Washington, D.C., while travelling a total of less than 11,000 miles doesn't seem to give you much of a hint as to what the route would be.

Your other two examples have the same families of variants. The standard Knapsack problem has a tarvet value $v$ and asks if your knapsack can carry items of total value at least $v$; OPT-Knapsack asks what is the greatest value you can carry. ILP asks if the linear inequations have an integer solution; OPT-ILP asks for the maximum solution. In both cases, the decision version of the problem is NP-complete and the optimization version is NP-hard.

$\endgroup$

Your Answer

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

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