Decision versus Optimization Problems

Complexity theory is framed around yes-or-no decision problems, but most practical tasks are optimization problems closely tied to them.

Two framings

A decision problem asks a yes-or-no question: "is there a tour shorter than L?" An optimization problem asks for the best value or structure: "what is the shortest tour?" Complexity classes like P and NP are defined on decision problems, because yes/no answers are clean to reason about.

Why decision problems are the standard

Decision problems have a single bit of output, which makes definitions of verification, reduction, and completeness tidy. An optimization problem's answer is a value or object, complicating what it means to "verify" or to have a short certificate. So theory reduces optimization to a sequence of decisions.

Turning optimization into decision

Any optimization problem has a decision version: add a threshold and ask whether a solution meeting it exists. "Minimize the tour length" becomes "is there a tour of length at most L?" Solving the decision version for many thresholds, via binary search, recovers the optimal value.

• Optimization: find the best solution and its value
• Decision: does a solution at least this good exist
• Search: produce an actual solution achieving the optimum

Hardness transfers

The decision version of an NP-hard optimization problem is typically NP-complete, while the optimization version is NP-hard but usually not in NP. This is why the traveling salesman decision problem is called NP-complete but finding the shortest tour is called NP-hard.

Self-reducibility

For many natural problems, a decision oracle can be used to construct an actual solution, not just its existence, by fixing choices one at a time and asking whether a solution still exists. This self-reducibility means the decision and search versions are equivalent in difficulty for practical purposes.