Decision problem (yes–no questions in computation)

Formalization

Formally, a decision problem specifies a domain of valid inputs and a predicate that maps each input to true (yes) or false (no). A decision procedure is an effective algorithm that, given any valid input, halts and returns the correct yes/no answer. A problem is called decidable or computable if such a procedure exists. If no algorithm can decide the predicate for all inputs, the problem is undecidable. A related notion is semidecidability (recursively enumerable): there is an algorithm that halts and accepts for positive instances, but may never halt for negative ones.

Canonical examples

• Halting problem — deciding whether a given program halts on a given input; this is a classical undecidable problem.
• Boolean satisfiability (SAT) — determining whether a Boolean formula has a satisfying assignment; SAT is central in complexity theory and is the first known NP-complete decision problem.
• Graph connectivity and other basic graph properties — typically decidable and often solvable efficiently with polynomial-time algorithms.
• Primality testing (decision form) — deciding whether an integer is prime; decidable and known to admit efficient algorithms in practice.
• First-order logic validity — validity in first-order logic is undecidable in general, which was a key negative answer to Hilbert's Entscheidungsproblem.

Reductions and completeness

Decision problems are compared by reductions that transform instances of one problem into instances of another while preserving yes/no answers. Many-one (mapping) reductions and Turing reductions are two standard notions. Reductions allow the definition of hardness and completeness: a problem is complete for a complexity class if it belongs to the class and every problem in the class reduces to it. For example, NP-complete problems are decision problems to which every problem in NP can be reduced by a polynomial-time many-one reduction.

Decision vs. search

Some computational tasks are naturally phrased as search problems (find an object with a property) rather than decision problems (does one exist?). Many search problems have corresponding decision versions and the two formulations are closely related: efficient decision procedures can often be used to guide search and vice versa, but complexity classifications and the existence of reductions can differ depending on formulation.

Practical and theoretical significance

Decision problems provide a simple, uniform framework for reasoning about algorithm design, complexity bounds, and impossibility proofs. They underpin modern approaches to automated reasoning, satisfiability solving, formal verification and complexity-theoretic classification of tasks. Understanding which decision problems are decidable or tractable clarifies the limits of computation and informs the design of software tools used in verification, cryptography and artificial intelligence.

Further reading

Introductory treatments typically appear in textbooks and surveys on computability theory and computational complexity. For the philosophical and historical context of undecidability see material on Hilbert's problems and the Entscheidungsproblem, and for detailed accounts of reductions and classes consult standard expositions of NP-completeness and space-bounded classes. See also introductions to decidability and to problems of set membership for complementary perspectives.