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$.
Optimization problem vs decision problem - reduction
complexity theory;optimization;reductions;decision problem