Skip to interview prep
Apexed

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.

Why are complexity classes defined for decision problems, and how do they relate to optimisation problems — Data structures & algorithms interview question — Ap