patternMinor
Why is Knapsack and ILP NP-complete
Viewed 0 times
whyilpcompleteandknapsack
Problem
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.
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.
Solution
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:
Then there is the following optimization problem, MIN-TSP:
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.
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.
Context
StackExchange Computer Science Q#59528, answer score: 8
Revisions (0)
No revisions yet.