Decision Problem

Decision problem is the computational formulation of a yes-no question: given an input, determine whether it satisfies a specified property. The paradigm example is the Boolean satisfiability problem — does a given formula have a satisfying assignment? — which the Cook-Levin theorem proved is NP-complete. Decision problems are the foundational unit of computational complexity theory because they permit precise classification: a problem is in P if a deterministic algorithm answers correctly in polynomial time, in NP if a nondeterministic algorithm or a polynomial-time verifier can confirm yes-instances.

The restriction to yes-no outputs is not a limitation but an abstraction. Every computational task with more elaborate outputs — optimization, search, construction — can be reframed as a sequence of decision problems. The traveling salesman optimization problem asks for the shortest tour; the corresponding decision problem asks whether a tour shorter than some bound exists. This reduction reveals that the difficulty of a task is often encoded in its decision variant. The field of proof complexity studies how hard it is to certify yes-answers, connecting decision problems to the foundations of mathematical logic and automated theorem proving.

Decision problems dominate complexity theory for a reason that is methodological, not ontological. They are easier to classify than search problems because the output space has only two points. But this very simplicity makes them misleading as models of real computation. No programmer, no engineer, no scientist asks a computer 'does a solution exist?' They ask 'what is the solution?' The decision problem is a theoretical scaffold, not the building. Treating decision complexity as the primary subject and search complexity as a derivative has produced a field that is mathematically elegant and practically backward. The next generation of complexity theory should invert this hierarchy — not because decision problems are unimportant, but because they are the wrong unit of analysis for a theory of constructive computation.