2
$\begingroup$

There are many NP-complete decision problems that ask the question whether it holds for the optimal value that OPT=m (say bin packing asking whether all items of given sizes can fit into m bins of a given size). Now, I am interested in the problem whether OPT>m. Is this a decision problem or an optimization problem? It seems to be that it lies in NP (a NTM can guess a solution and it can be verified in polynomial time that the bound is met). Is it also NP-complete?

I would have said yes, because having a polynomial algorithm, we could find a solution in polynomial time for the original problem (asking whether OPT=m) by using binary search and repeatedly using the polynomial algorithm to test if OPT larger than some bound.

However when I try to construct a proper solution, I always see the complication that the oracle (that asks whether OPT>m') would need to be queried more than once, and this is forbidden in the polynomial time Karp reduction.

Any solutions or remarks? Would it make a difference if I ask whether OPT>=m?

Thanks in advance

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ What problem(s) are you considering? Whether you take $\leq$ or $\geq$ does not matter in principle; consider e.g. the decision version of longest path or any other NP-hard maximisation problem. $\endgroup$
    – Raphael ♦
    Mar 25, 2013 at 15:20
  • $\begingroup$ Bin packing for instance, does it matter (for the complexity) if I cosider > or >= instead of =? $\endgroup$
    – user2145167
    Mar 25, 2013 at 21:43

2 Answers 2

Reset to default
1
$\begingroup$

Is OPT = m? is a coNP decision problem. A "no" answer has a certificate verifiable in polynomial time, the certificate being a valid bin packing that uses fewer than $m$ bins.

The same is true for the question Is OPT > m?. There is no polynomial-time verifiable certificate for the "yes" answer to either of these questions unless NP = coNP.

Is OPT < m? is an NP decision problem. A "yes" answer has a certificate verifiable in polynomial time, the certificate being a valid bin packing that uses fewer than $m$ bins.

Improve this answer
$\endgroup$
3
  • $\begingroup$ So, for the last Np decision problem version, I could have asked as well if OPT<=m? $\endgroup$
    – user2145167
    Mar 26, 2013 at 17:26
  • $\begingroup$ Yes. OPT <= m can be rewritten as OPT < m + 1, so the question remains in NP. $\endgroup$
    – Kyle Jones
    Mar 26, 2013 at 18:22
  • $\begingroup$ Just one more question about the directions to fully understand this: given a maximization problem, do I always ask OPT>m in the corresponding NP decision problem; and given a minimization problem, do I always ask OPT<m in the NP decision problem? $\endgroup$
    – user2145167
    Mar 27, 2013 at 10:01
1
$\begingroup$

One way to show hardness of the decision version of an optimization problem (i.e., $OPT \geq m'$) given that the standard decision version (i.e., $OPT = m$) is NP-complete is by using Turing reductions in both directions.

Therefore, you need to do two things:

(1) Show that if you have a poly-time oracle that can solve the $OPT = m$ problem, then with a polynomial number of calls to it, you can solve the $OPT \geq m'$ problem. This is usually the non-trivial part of these reductions.

(2) Show that if you have a poly-time oracle that can solve the $OPT \geq m'$ problem, then with a polynomial number of calls to it, you can solve the $OPT = m$ problem. This is trivial using binary search in most cases.

Just a side note: Of course it is not always true that if $OPT=m$ is hard, that $OPT \geq m'$ is also hard. One simple example is the subset product problem -- it is hard to tell if there is a subset with product $= T$, but easy to tell if there is a subset with product $\geq T'$ (just multiply all terms together, this is the MAX product you can get).

However, if you state the optimization problem as finding the largest product $T'$ that is smaller than $T$, the problem is hard again. So, how you state your optimization problem is very important.

Improve this answer
$\endgroup$
4
  • $\begingroup$ But is it possible to use Turing reductions for showing NP-hardness? I thought you can only do this with many-one reductions because NP is not closed under Turing reductions and any problem in co-NP has a Turing reduction to any NP-complete problem (from en.wikipedia.org/wiki/Polynomial-time_reduction)? $\endgroup$
    – user2145167
    Mar 26, 2013 at 11:40
  • $\begingroup$ This is why you do the Turing reduction in both directions and require that the original decision version is NP-complete. $\endgroup$
    – RDN
    Mar 26, 2013 at 11:47
  • $\begingroup$ Do you know a good reference for this? Not that I don't believe this, but I am interested in this. $\endgroup$
    – user2145167
    Mar 26, 2013 at 13:02
  • $\begingroup$ My go to book for this stuff is: "Theory of Computational Complexity" by Ker-I Ko. Perhaps there is a PDF version online. $\endgroup$
    – RDN
    Mar 26, 2013 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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