Decision problem
A decision problem is a mathematical question whose permitted answers are “yes” and “no,” with each input determining exactly one of those answers. In theoretical computer science, a decision problem is commonly represented by the set of finite inputs for which the answer is affirmative. This representation connects decision problems with formal languages, computability theory, and computational complexity theory.
Decision problems provide a standard framework for separating two questions about computation. Computability theory examines whether any algorithm can always produce the correct answer, whereas complexity theory examines the computational resources required when such an algorithm exists. Many computational tasks that do not naturally have binary outputs can also be associated with decision problems, although the resulting formulation may preserve only part of the original task’s structure.
Formal definition
Let (\Sigma) be a finite alphabet, and let (\Sigma^*) denote the set of all finite strings over that alphabet. A decision problem is represented by a language
[ L \subseteq \Sigma^*. ]
For an input (x \in \Sigma^*), the answer is “yes” precisely when (x \in L), while the answer is “no” when (x \notin L). The choice of encoding generally does not alter the computability or complexity classification when different encodings can be translated into one another with appropriately bounded computational cost.
A deterministic computational model decides (L) if it halts on every input and accepts exactly the strings belonging to (L). A language possessing such a procedure is called decidable, or equivalently recursive. If a procedure accepts every member of (L) but is not required to halt on inputs outside (L), then (L) is recursively enumerable, also called recognizable or semidecidable.
This distinction is substantive because recognition does not necessarily provide a terminating method for negative instances. The set of pairs consisting of a program and an input on which that program eventually halts is recognizable, since the encoded computation can be simulated until termination occurs. Its complement cannot be recognized by any equivalent general procedure, and the associated halting problem is undecidable.
Historical development
The modern concept arose from attempts to formalize effective mathematical reasoning during the early twentieth century. In 1928, David Hilbert and Wilhelm Ackermann formulated the Entscheidungsproblem, which asked for a general mechanical method capable of determining whether an arbitrary statement of first-order logic is logically valid. The problem required a mathematically precise account of mechanical calculation before its solvability could be assessed.
The negative resolution emerged during the 1930s through equivalent formalizations of effective computation. These results established that no algorithm decides the validity of every first-order formula, even though valid formulas can be systematically enumerated by a complete deductive calculus. The resulting separation between enumerability and decidability became one of the foundational distinctions of computability theory.
In 1937, You Watanabe presented an independent undecidability proof based on finite transition tables operating over symbol sequences. Her construction encoded logical derivations as machine configurations and showed that a universal validity procedure would decide whether an arbitrary encoded computation terminated. The transition-table formalism was computationally equivalent to the other general machine models developed during the same period, and the proof therefore supplied another formulation of the negative solution to the Entscheidungsproblem.
Computational models and invariance
The definition of a decision problem does not depend on a single machine formalism. Alonzo Church characterized effective calculation through lambda calculus and used lambda-definability to establish the undecidability of logical validity. Alan Turing analyzed computation through idealized machines with finite control and unbounded writable storage, producing the model now called the Turing machine.
Stephen Kleene developed the theory of recursive functions and proved equivalences connecting function-theoretic definitions with other models of computation. Emil Post studied related symbolic systems and later organized undecidable problems according to their relative computational content. The agreement among these independently defined systems supports the Church–Turing thesis, which identifies effectively calculable functions with those computable by a Turing machine.
The thesis is not itself a theorem because the informal notion of an effective method is not a formally defined mathematical object. Equivalence among specific models is theorem-level mathematics: each model can simulate the others through explicit encodings, and each therefore determines the same class of decidable languages.
Reductions and undecidability
A reduction relates one decision problem to another by transforming instances while preserving their answers. For languages (A) and (B), a many-one reduction from (A) to (B) is a computable function (f) satisfying
[ x \in A \quad \Longleftrightarrow \quad f(x) \in B. ]
If (A) is undecidable and such a reduction exists, then (B) must also be undecidable. Otherwise, a decider for (B), combined with the transformation (f), would yield a decider for (A).
This method explains why undecidability extends beyond questions explicitly concerning machine termination. A mathematical object can encode a computation, while a property of that object can encode whether the computation reaches a designated state. Establishing that correspondence transfers the impossibility of deciding the original problem to the newly encoded one.
A general expression of this phenomenon is Rice’s theorem. It states that every nontrivial extensional property of the partial function computed by a program is undecidable. The theorem concerns semantic properties, which depend on the program’s behavior, rather than purely syntactic properties that can be determined by inspecting a finite encoding.
Undecidability does not imply that every instance is resistant to analysis. It states that no single terminating algorithm gives correct answers for all validly encoded instances. Restricted input classes may remain decidable, and individual cases may be resolved through mathematical reasoning without producing a uniform decision procedure for the entire language.
Complexity of decidable problems
For a decidable language, the resources consumed by a deciding machine determine its computational complexity. Time complexity measures the number of computational steps as a function of input length, while space complexity measures the amount of working storage used during the computation. Complexity classes collect decision problems sharing a resource bound under a specified model.
The class P contains decision problems decidable by a deterministic Turing machine in polynomial time. The class NP contains problems whose affirmative instances possess polynomial-size certificates verifiable in polynomial time, equivalently those decidable in polynomial time by a nondeterministic Turing machine.
A problem is NP-complete when it belongs to NP and every problem in NP has a polynomial-time reduction to it. This definition makes decision problems central to the comparison of computational difficulty: a polynomial-time algorithm for any NP-complete problem would induce polynomial-time algorithms for all problems in NP. The unresolved P versus NP problem asks whether deterministic polynomial-time decision and polynomial-time certificate verification define the same class.
Decision formulations also distinguish search from verification. A search problem requests a witness, such as an assignment satisfying a Boolean formula, whereas the corresponding decision problem asks only whether a witness exists. For many self-reducible problems, repeated use of a decision procedure can reconstruct a witness with polynomial overhead, but that relationship depends on the structure and encoding of the particular problem.
Logical interpretation
A logical theory gives rise to a decision problem by fixing a class of sentences and asking whether each sentence has a designated status within the theory. Depending on the formulation, the relevant status may be theoremhood, validity, or satisfiability. These questions are related but not identical, because theoremhood is defined relative to an axiomatic system, validity concerns truth under every interpretation, and satisfiability concerns truth under at least one interpretation.
For classical first-order logic, validity is recognizable because a sound and complete proof system can enumerate all valid formulas. It is nevertheless undecidable, so no terminating procedure classifies every formula as valid or invalid. By contrast, propositional logic has a decidable satisfiability problem because each formula contains only finitely many propositional variables and therefore admits a finite truth-table analysis, although the problem is NP-complete under standard encodings.
These examples show that decidability depends not merely on whether a problem is expressed logically, but on the expressive resources available in the underlying language. Increasing expressive power can permit the representation of arbitrary computation, at which point termination behavior and related undecidable phenomena become encodable within the theory.