# How do you prove that a solution to the 0-1 knapsack problem is optimal?

Given a boolean vector b representing a solution to the knapsack problem with n elements k capacity and where each element has integer weight and value.

Proving that the solution is a solution is trivial. You add all the weights multiplied by the selection coefficient and check if it adds to more than the capacity.

But how do I verify that the solution given is optimal?

You can't, not efficiently (unless P=NP).

Suppose there was a polynomial-time algorithm $$A$$ to check whether a given solution is optimal.

Then there would be a polynomial-time algorithm to solve the knapsack decision problem, i.e., given a problem instance and a value $$V$$, check whether there exists any solution with value $$>V$$. Here is how: you add a single extra element with value $$V$$ and weight equal to the capacity; this then gives a trivial solution of value $$V$$; and now you run $$A$$ on this modified problem instance. If $$A$$ says "not optimal", then there exists a solution of value $$>V$$ to the original instance; otherwise, there does not.

This would also imply that there exists a polynomial-time algorithm to find the optimal solution for a knapsack problem. Here is how: you use binary search on $$V$$, and apply the algorithm for the decision problem in each iteration of binary search.

That would imply that $$P=NP$$.

So if there exists a polynomial-time algorithm to check optimality, we obtain a proof that $$P=NP$$. Conversely, if we assume $$P \ne NP$$, then there does not exist any polynomial-time algorithm to check optimality.

• So what you are saying is, when someone answers my question we can go collect a turing award. Jul 20 at 5:06
• @Makogan, nice way to put it! I like your optimism :)
– D.W.
Jul 20 at 5:16
• However there should be a pseudo polynomial verifier if the sizes of the integers are small, no? Jul 20 at 5:39
• @Makogan, yes, you can just solve the knapsack problem from scratch to find its optimal solution in pseudo polynomial time.
– D.W.
Jul 20 at 17:32