1
$\begingroup$

Consider the following problem. Given a set of $n$ items having weight $w_i$ and value $v_i$ and a maximum capacity $W$, maximize $\sum\limits_{i=1}^n a _i v_i$ under $\sum\limits_{i=1}^n a_i w_i \leq W$ where $a_i \in \{0,1\}$. That is, choose a subset of items giving the maximum total value while still fitting into the capacity. I am wondering what the time complexity of this problem is and I think that I found that it is not in NP. The reason is that there can be no certificate of correctness for any one particular choice of items. When someone gives me a set I cannot simply check to see that it indeed gives maximum value.

It seems that this problem is at least as hard to check as it is to solve, so it cannot be in NP.

Another line of reasoning leads me to the following: The decision problem can a value of at least $V$ be achieved can be checked in polynomial (actually linear) time by a certificate giving a list of the items. Now a machine can first add up all the values to get $V_{\max}$, and then perform the decision problem for $V = 1, \ldots, V_{\max}$ until the answer is no, having then maximized the sum. This would I guess be an NP computation as we run $V_{\max}$ NP computations and $V_{\max}$ grows linearly with the input.

Hmm, help would be appreciated.

$\endgroup$
  • $\begingroup$ Well, I don't know why you used word "therefore" because if problem can be checked in polynomial time, it also is in EXP. $\endgroup$ – rus9384 Sep 29 '17 at 15:50
  • $\begingroup$ Ow yes you are right, my question stands though and I will update $\endgroup$ – Slugger Sep 29 '17 at 15:55
  • $\begingroup$ Well, optimization problems can't be in NP, since they are not decision problems. Whether or not this problem is in FNP is open problem in CS, but it is suspected that NPO problems are not in FNP. But surely your problem is in $P^{NP}$. $\endgroup$ – rus9384 Sep 29 '17 at 16:00
  • $\begingroup$ Thank you, that is as I expected, but then what is wrong with the argument in my last paragraph? $\endgroup$ – Slugger Sep 29 '17 at 16:01
  • 1
    $\begingroup$ It is correct, you actually proved that you can use $P^{NP}$ machine to solve your problem (actually use a decision version of problem polynomially many times). $\endgroup$ – rus9384 Sep 29 '17 at 16:04

Your Answer

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

Browse other questions tagged or ask your own question.