Polynomial time reductions using binary search

Question

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

• Raphael: 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.
• user2145167: Bin packing for instance, does it matter (for the complexity) if I cosider > or >= instead of =?

Answer 1

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.

• user2145167: So, for the last Np decision problem version, I could have asked as well if OPT<=m?
• Kyle Jones: Yes. OPT <= m can be rewritten as OPT < m + 1, so the question remains in NP.
• user2145167: 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?

Answer 2

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.

• user2145167: 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)?
• RDN: This is why you do the Turing reduction in both directions and require that the original decision version is NP-complete.
• user2145167: Do you know a good reference for this? Not that I don't believe this, but I am interested in this.
• RDN: My go to book for this stuff is: "Theory of Computational Complexity" by Ker-I Ko. Perhaps there is a PDF version online.