1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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