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$.

  • 4
    $\begingroup$ Is your question answered by this or that question? (Why would binary search not work for other problems?) $\endgroup$ – Raphael Aug 1 '12 at 21:45

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.


Your Answer

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

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