Fact-checked by Grok 2 weeks ago

Decision problem

In , a decision problem is a computational question that requires a yes-or-no answer, typically phrased as whether a given input satisfies a specified property or belongs to a particular set, and is formally analyzed to determine if an can solve it for all possible inputs. These problems form the foundation of studying what can and cannot be computed algorithmically, distinguishing between decidable problems (solvable by a that always halts with the correct answer) and undecidable ones (no such algorithm exists). The origins of decision problems trace back to David Hilbert's 1928 lecture, where he posed the (decision problem) as a challenge to find a mechanical procedure for verifying the provability of any statement in first-order predicate logic, as part of his broader program to formalize mathematics. In 1936, resolved this negatively by introducing —a formal consisting of an infinite tape, a reading/writing head, and a finite set of states—and using a argument to prove that no general decision procedure exists for the , as it would imply solving the undecidable . Independently, developed and showed the same result, establishing the Church-Turing thesis that equates effective with solvability. Key examples of decision problems include the , which asks whether a Turing machine will halt (terminate) on a given input, proven undecidable by Turing through a self-referential contradiction; this demonstrates inherent limits on algorithmic prediction of program behavior. Other notable undecidable problems are (determining solvability of Diophantine equations, resolved negatively in 1970 by building on earlier work) and the (whether two words in a finitely presented group represent the same element). Decision problems also underpin , where solvable ones are classified by resources like time (e.g., P vs. NP) and space, influencing fields from to .

Fundamentals

Definition

In and , a decision problem is a question posed within a , where the input consists of a finite over a finite , and the expected output is a answer of "yes" or "no" indicating whether the input satisfies a specified property. This formulation ensures that decision problems are precisely defined, allowing for the study of algorithmic solvability without ambiguity in the response format. Formally, a decision problem D is represented as a of \Sigma^*, the set of all finite strings over a finite \Sigma, where membership in D corresponds to the "yes" instances of the problem, and non-membership to the "no" instances. This set-theoretic view aligns decision problems with the recognition of formal languages, facilitating analysis via models like Turing machines, which accept or reject inputs to decide membership. Unlike general computational problems, which may produce multi-valued outputs, continuous results, or require constructing solutions, decision problems are restricted to binary outcomes, enabling focused investigations into decidability and resource bounds. The concept was introduced in the 1930s by and as part of their work on the , Hilbert's challenge to determine the provability of mathematical statements algorithmically. Understanding decision problems presupposes familiarity with formal languages, where inputs are encoded as strings, and basic notions, such as algorithmic procedures for .

Examples

One prominent example of a decision problem is the , which asks whether a given will halt (i.e., terminate) on a specified input. In this formulation, the input consists of a description of the and its initial tape contents, and the expected output is yes if the machine eventually stops and no otherwise. Another classic instance arises in : primality testing, which determines whether a given positive n > 1 is a . Here, the input is the integer n, and the answer is yes if n has no positive divisors other than 1 and itself, and no otherwise; while decidable, this problem posed significant computational challenges historically due to the need for efficient algorithms. In , the validity problem for asks whether a given is true in every possible model ( interpreting the ). The input is the , and the output is yes if it is valid (a in all interpretations) and no if there exists a counter-model. This formulation, known as the , exemplifies decision problems in formal systems. From , the Hamiltonian cycle problem inquires whether an undirected graph contains a that visits each exactly once and returns to the starting . The input is the graph's and edge sets, with yes if such a exists and no otherwise. These examples, drawn from , arithmetic, logic, and , demonstrate the breadth of decision problems as yes/no questions about specific instances.

Decidability

Decidable Problems

A decision problem is decidable if there exists a Turing machine that, given any input, halts in finite time and outputs the correct yes or no answer for every possible instance of the problem. This means the algorithm terminates with acceptance for yes-instances and rejection for no-instances, without looping indefinitely. The Church-Turing thesis provides the foundational justification for using Turing machines as the standard model of computation in this context; it informally asserts that any function that can be effectively computed by a human following an algorithm can be computed by a Turing machine. Under this thesis, decidability captures all problems solvable by mechanical procedures. To prove that a decision problem is decidable, one common method is direct construction of an algorithm, such as the , which determines whether a given greater than is prime in deterministic polynomial time. Another approach is : if a problem can be transformed in polynomial time to another known decidable problem, then it is also decidable, preserving the halting guarantee. A classic example is the acceptance problem for finite automata: given a deterministic finite automaton and a string, it is decidable whether the automaton accepts the string, since the finite state space allows simulation in linear time relative to the input length, and regular languages are precisely those recognized by such automata. states that every non-trivial of the languages recognized by Turing machines is undecidable. Trivial properties—those that either all or no such languages satisfy—are decidable, since the answer is independent of the specific machine. All decidable problems are computable, meaning they correspond to recursive functions that halt on every input, though the can from to highly inefficient, depending on the problem. In contrast to undecidable problems like the , decidable ones guarantee termination and correctness for all inputs.

Undecidable Problems

A decision problem is undecidable if no exists that halts on every input and correctly outputs yes or no according to whether the input satisfies the problem's condition; on some inputs, any such machine must either give an incorrect answer or run indefinitely. This notion captures the fundamental limits of algorithmic solvability, distinguishing undecidability from mere computational inefficiency. The exemplifies undecidability: given a description of a and an input, determine whether the halts on that input. proved its undecidability in using a argument. Suppose a hypothetical halting oracle H(M, i) exists that decides if M halts on input i. Construct a D that, on input e (encoding M_e), simulates H(M_e, e): if H says yes, D loops forever; if no, D halts. Now apply D to its own encoding: if H(D, e) says yes (meaning D halts on e), then D loops, a contradiction; if no, D halts, another contradiction. Thus, no such H exists. Rice's theorem, proved by Henry Gordon Rice in 1953, provides a broad class of undecidable problems. It states that for any non-trivial P of the language recognized by —meaning P holds for some but not all such languages—the problem of deciding whether a given recognizes a language in P is undecidable. The proof reduces the to membership in P by constructing machines that append irrelevant computations to known halting or non-halting behaviors while preserving the property. This theorem implies that properties like "does the machine accept any string?" or "is the language ?" (for ) are undecidable, except for trivial cases like always accepting the empty language. Alonzo Church independently showed in 1936 that the —determining whether a formula is provable from given axioms—is undecidable, using the to encode computations and reducing it to his earlier result on the unsolvability of an analogous number-theoretic problem. Similarly, Emil Post demonstrated in 1946 that the is undecidable: given pairs of strings over an alphabet, decide if there exists a sequence of indices such that the concatenations from the top and bottom rows match. The proof reduces the to by encoding machine simulations into string matches, where a solution corresponds to a halting computation. These undecidability results impose strict limits on and in , as no general can prove arbitrary properties of programs, requiring instead domain-specific approximations, bounded checks, or manual proofs to mitigate risks in critical systems.

Complexity Aspects

Complexity Classes

Decidable decision problems are classified into complexity classes based on the computational resources required to solve them, primarily time and space bounds on . The class \mathsf{DTIME}(f(n)) consists of all decision problems solvable by a deterministic in at most O(f(n)) time steps on inputs of length n . Similarly, \mathsf{DSPACE}(f(n)) includes problems solvable using O(f(n)) . These classes form the foundation of resource-bounded , distinguishing problems by efficiency rather than mere decidability. Key complexity classes for polynomial resources include \mathsf{P}, the union over k \geq 1 of \mathsf{DTIME}(n^k), capturing problems solvable in polynomial time . The class \mathsf{NP} comprises problems where "yes" instances have polynomial-time verifiable certificates using nondeterministic Turing machines, formally the union over k \geq 1 of \mathsf{NTIME}(n^k) . \mathsf{PSPACE} is the union over k \geq 1 of \mathsf{DSPACE}(n^k), encompassing problems solvable with space, potentially requiring exponential time . These classes highlight trade-offs, such as \mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{PSPACE}, with open questions like whether \mathsf{P} = \mathsf{NP}. Hierarchy theorems establish strict separations within these frameworks. The time hierarchy theorem proves that for suitable f(n), \mathsf{DTIME}(f(n)) \subsetneq \mathsf{DTIME}(f(n)^2), demonstrating that more time allows solving strictly harder problems . Analogous space hierarchy theorems show \mathsf{[DSPACE](/page/DSpace)}(f(n)) \subsetneq \mathsf{[DSPACE](/page/DSpace)}(f(n) \log f(n)) for space-constructible f(n) . These results imply infinite strict inclusions, such as \mathsf{[P](/page/P′′)} \subsetneq \mathsf{[EXP](/page/Exp)}. Oracle machines extend Turing machines with access to an for a fixed , enabling relative computations between classes. The seminal relativization results construct oracles A and B such that \mathsf{P}^A = \mathsf{NP}^A relative to A, but \mathsf{P}^B \neq \mathsf{NP}^B relative to B, indicating that relativizing proof techniques cannot resolve \mathsf{P} vs. \mathsf{NP} . Such separations underscore limitations in diagonalization methods for class equalities. Modern extensions incorporate alternative computational models, such as s. The class \mathsf{[BQP](/page/BQP)} includes decision problems solvable with bounded error by a quantum Turing machine in polynomial time, potentially offering speedups over classical classes for certain problems like factoring . Undecidability marks the beyond which no recursive can reach, as undecidable problems evade all resource bounds.

Complete Problems

In , a decision problem is said to be complete for a if it belongs to the class and every problem in that class can be reduced to it in polynomial time, making it a "hardest" problem within the class that serves as a for studying the class's properties. This notion of completeness was formalized by in 1971, who introduced Cook-Turing completeness using polynomial-time many-one reductions for the class , demonstrating that the (SAT) is NP-complete. These reductions preserve membership: an instance of a problem A reduces to an instance of B if solving B allows solving A in polynomial time, establishing equivalence in hardness. The canonical NP-complete problem is SAT, which asks whether there exists an assignment of truth values to variables in a Boolean formula that makes the formula true. proved SAT's NP-completeness by showing that any verification problem reduces to SAT via a polynomial-time that constructs a formula encoding the machine's computation path. A restricted variant, 3-SAT, limits clauses to exactly three literals and is also NP-complete; Karp demonstrated this in 1972 by providing a polynomial-time from general SAT to 3-SAT, which introduces auxiliary variables to break larger clauses into conjunctions of three-literal clauses without altering satisfiability. This makes 3-SAT a standard example due to its simplicity and frequent use in algorithms and proofs. Karp reductions, also known as polynomial-time many-one , extend Cook's framework by showing that numerous combinatorial problems—such as the traveling salesman problem and —are NP-complete through chains of such reductions from SAT, highlighting the broad applicability of completeness in unifying disparate hard problems. For other classes, completeness follows analogous definitions: the quantified Boolean formulas (QBF) problem, which determines the truth value of a Boolean formula with alternating quantifiers over all variables, is PSPACE-complete, as shown by Larry Stockmeyer and Meyer in 1973 via that encode computations. Similarly, EXP-complete problems include those like the acceptance problem for deterministic Turing machines bounded by exponential time, where hardness arises from encoding computations that require resources. The implications of are profound: if any NP-complete problem like SAT lies in , then the entire class equals , collapsing the and resolving the P=NP in the affirmative, a central open question in the field since Cook's work. This property holds generally for complete problems in other classes, such as or , where solvability in a lower class would imply class equalities.

Related Problem Types

Function Problems

In computability theory, a function problem consists of specifying a function f that maps inputs from a domain (typically strings or natural numbers) to outputs (such as strings, numbers, or tuples), where the task is to compute f(x) for a given input x. A function problem is computable if there exists a Turing machine that, on input x, halts and produces the correct output f(x) whenever x is in the domain of f. This definition extends the notion of decision problems, which are special cases of function problems where the output is restricted to a binary value (yes or no, often encoded as 0 or 1). Function problems may be partial, meaning f(x) is defined only for some inputs, or total, meaning f is defined for all inputs in the domain. For partial functions, the corresponding must halt on inputs where f is defined but may loop indefinitely otherwise. Total computable functions correspond to those computable by that always halt, forming the class of total recursive functions. Classic examples illustrate the distinction. In , the function problem requires outputting the prime factors of a given n > 1, which is computable via exhaustive search but practically challenging for large n. For the traveling salesman problem, the function version outputs the length of the shortest tour visiting all cities in a given weighted , again computable but resource-intensive. These examples highlight how function problems demand producing explicit outputs, unlike their decision counterparts (e.g., "does n have a less than k?"). The theoretical foundation for computable function problems lies in recursive function theory. Stephen Kleene formalized general recursive functions in the 1930s as those obtainable from basic functions (zero, successor, and projections) via composition, primitive recursion, and minimization, showing equivalence to Turing computability. Primitive recursive functions form a proper subclass, defined similarly but without minimization, ensuring total computability and capturing many intuitive arithmetic operations, as introduced by Kurt Gödel. In modern applications, particularly , function problems appear as one-way functions: total computable functions f that are easy to evaluate but computationally infeasible to invert on average (i.e., finding x given f(x) is hard). Such functions underpin , assuming their existence enables secure systems like protocols.

Optimization Problems

Optimization problems seek to find the best solution from a set of feasible solutions according to a specified objective function, such as minimizing cost or maximizing efficiency, in contrast to decision problems that only require a yes/no answer regarding the existence of a solution satisfying certain conditions. These problems arise in fields like and , where the goal is to optimize a measure over a combinatorial structure. In , optimization problems are frequently studied via their corresponding decision versions to classify hardness, as decision problems provide a cleaner framework for defining classes like . The decision version of an typically asks whether there exists a feasible solution whose objective value meets or exceeds a given , such as "is there a solution with cost at most k?". Solving the decision problem in time often allows solving the in time via binary search over possible , establishing their equivalence in complexity up to polynomial factors. A classic example is the Traveling Salesman Problem (TSP), where the optimization variant requires finding the shortest Hamiltonian in a weighted graph, while the decision variant queries whether a of length at most k exists; the latter was proven NP-complete by from the Hamiltonian Cycle problem. Similarly, the optimizes the maximum value under weight constraints, with its decision version—does a subset exist with value at least v and weight at most w?—also NP-complete. When the decision version is NP-complete, the is NP-hard, implying no efficient exact algorithm exists unless P = NP, motivating approximation algorithms and heuristics for practical instances.