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