Optimization problem vs decision problem - reduction

Question

Assume we have an optimization problem with function $f$ to maximize.

Then, the corresponding decision problem 'Does there exist a solution with $f\ge k$ for a given $k$?' can easily be reduced to the optimization problem: calculate the optimal solution and check if it is $\ge k$.

Now, I was wondering, is it always possible to do the reduction (in polynomial time) the other way around?

For an example consider MAX-SAT: to reduce the optimization problem to the decision problem we can do a binary search in the integer range from 0 to the number of clauses. At each stoppage $k$ we check, with the decision problem solver, if there is a solution with $\ge k$.

Answer 1

There are a few conditions you would need to specify for this to even work, most importantly, that your function does have a maximum, otherwise you could try all k and end up going off into infinity. Likewise, you'd probably need to assume that f is only producing outputs on the integers or some other countable set.

If we're doing any sort of binary search, I think it is going to be exponential in the worst case unless we know an upper bound to start with. Assuming f returns numbers, finding the upper bound is going to be linear in terms of the maximum value. However, that means it's exponential in terms of the string-representation of the maximum value.

If we know an upper bound for the maximum of f, I can't see any reason why you couldn't do binary search to find it, but even then, it is polynomial in the upper bound, and could still be exponential in the length of the input, as opposed to the output.

Answer 2

An answer to this precise question is given by Bellare and Goldwasser, "The Complexity of Decision Versus Search", SIAM Journal on Computing, 23:1 (February 1994), DOI /10.1137/S0097539792228289; a more expository version of the above is Bellare's class note on this. The short answer is that if the decision problem is NP-complete, the search problem is "NP-complete" (really: can't do much better than an exhaustive search) also; however, if the search problem is harder, the decision problem can even be in P (can check there is a solution very easily) if a plausible conjecture in complexity theory is true.