Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
