392. Why are complexity classes defined for decision problems, and how do they relate to optimisation problems?
EasyComplexity classes
Technical
Show model answer
Decision problems have yes/no answers, which makes reductions and certificates clean. An optimisation problem ('find the shortest tour') has a decision version ('is there a tour of length at most k?'). If you can solve the optimisation problem, the decision version is immediate; conversely, binary search on k, with polynomially many decision calls when the numbers have polynomially many bits, recovers the optimal value.
Often you can also recover the solution itself by self-reduction: for SAT, fix variables one at a time and ask the decision oracle whether the remaining formula is still satisfiable. So the decision and optimisation versions are polynomially equivalent for most natural NP problems.