Decision problem

In recursion theory and computational complexity theory, a decision problem is a yes-or-no question on specified sets of inputs. For example, the problem "given two natural numbers x and y, does x evenly divide y?" is a decision problem. The answer can be either 'yes' or 'no', and depends upon the values of x and y.

Decision problems are closely related to function problems, which are the quiestions that can have answers that are more complex than a simple 'yes' or 'no': every dicision problem can be converted into an equivalent function problem; every function problem can be convereted into an equivalent decision problem. For instance, one can straightforwardly show that the decision problem "given two numbers x and y, does x evenly divide y?" can be converted into the function problem "given two numbers x and y, what is x divided by y?" and vice versa.

A decision procedure (or decision algorithm) of a given decision problem is an effective procedure that determines the answer of the decision problem for every value of the parameters in the decision problem. For instance, a decision procedure for the decision problem "given two numbers x and y, does x evenly divide y?" would explain how to determine whether x evenly divides y, given x and y for every value of "x" and "y". One example of such procedures is taught to all school children and is called "long division." When a decision problem has some decision procedure, such as in this example, the problem is said to be decidable.

The field of computational complexity theory categorizes decidable decision problems by how difficult they are to solve. "Difficult", in this sense, is described in terms of the computational resources needed by the most efficient algorithm for a certain problem. The field of recursion theory, meanwhile, categorizes undecidable decision problems by Turing degree, which is a measure of the noncomputability inherent in any solution.

Definition

A decision problem is any arbitrary yes-or-no question on specified sets of inputs. Because of this, it is common to define the decision problem in terms of the set of inputs for which the problem returns yes. The problem "given two natural numbers x and y, does x evenly divide y?", and the problem "given a sequence x of English alphabets, is there any occurrence of "aa"?" are examples of decision problem.

Formally, a decision problem is a subset A of the natural numbers. By using Gödel numbers, it is possible to study other sets such as formal languages. The informal "problem" is that of deciding whether a given number is in the set.

A decision problem is called decidable or effectively solvable if A is a recursive set. A problem is called partially decidable, semidecidable, solvable, or provable if A is a recursively enumerable set. Partially decidable problems and any other problems that are not decidable are called undecidable.

Definition

A decision problem is any arbitrary yes-or-no question on an infinite set of inputs. Because of this, it is traditional to define the decision problem in terms of the set of inputs for which the problem returns yes. In this sense, a decision problem is equivalent to a formal language.

Formally, a decision problem is a countable set S and a function

$f:S\to \lbrace 0,1\rbrace$.

Let A be the preimage of f for 1.

$A:=\lbrace s\in S|f(s)=1\rbrace =f^{-1}(\lbrace 1\rbrace )$

The problem is called decidable if A is a recursive set. It is called partially decidable, solvable or provable if A is a recursively enumerable set. Otherwise, the problem is called undecidable.

We can give an alternative definition in terms of computable functions:

If f is a total computable function, the problem is called computable. If f is only a partial computable function, the problem is called partially computable. Otherwise, the problem is called uncomputable.

Examples

A classic example of a decidable decision problem is the set of prime numbers. It is possible to effectively decide whether a given natural number is prime by testing every possible nontrivial factor. Although much more efficient methods of primality testing are known, the existence of any effective method is enough to establish decidability.

Important undecidable decision problems include the halting problem; for more, see list of undecidable problems. In computational complexity, decision problems which are complete are used to characterize complexity classes of decision problems. Important examples include the boolean satisfiability problem and several of its variants, along with the undirected and directed reachability problem.

History

The Entscheidungsproblem, German for "Decision-problem", is attributed to David Hilbert: "At [the] 1928 conference Hilbert made his questions quite precise. First, was mathematics complete... Second, was mathematics consistent... And thirdly, was mathematics decidable? By this he meant, did there exist a definite method which could, in principle be applied to any assertion, and which was guaranteed to produce a correct decision on whether that assertion was true" (Hodges, p. 91). Hilbert believed that "in mathematics there is no ignorabimus' (Hodges, p. 91ff) meaning 'we will not know'. See David Hilbert and Halting Problem for more.

Equivalence with function problems

A function problem consists of a partial function f; the informal "problem" is to compute the values of f on the inputs for which it is defined.

Every function problem can be turned into a decision problem; the decision problem is just the graph of the associated function. (The graph of a function f is the set of pairs (x,y) such that f(x) = y.) If this decision problem were effectively solvable then the function problem would be as well. This reduction does not respect computational complexity, however. For example, it is possible for the graph of a function to be decidable in polynomial time (in which case running time is computed as a function of the pair (x,y) ) when the function is not computable in polynomial time (in which case running time is computed as a function of x alone). The function f(x) = 2^x has this property.

Every decision problem can be converted into the function problem of computing the characteristic function of the set associated to the decision problem. If this function is computable then the associated decision problem is decidable. However, this reduction is more liberal than the standard reduction used in computational complexity (sometimes called polynomial-time many-one reduction); for example, the complexity of the characteristic functions of an NP-complete problem and its co-NP complete complement is exactly the same even though the underlying decision problems may not be considered equivalent in some typical models of computation.

References

ISBN links support NWE through referral fees

• Hanika, Jiri. Search Problems and Bounded Arithmetic. PhD Thesis, Charles University, Prague. http://eccc.hpi-web.de/pub/eccc/theses/hanika.pdf.
• Hodges, A., Alan Turing: The Enigma, Simon and Schuster, New York. Cf Chapter "The Spirit of Truth" for some more history that led to Turing's work.

Hodges references a biography of David Hilbert: Constance Reid, Hilbert (George Allen & Unwin; Springer-Verlag, 1970). There are apparently more recent editions.

• Kozen, D.C. (1997), Automata and Computability, Springer.
• Hartley Rogers, Jr., The Theory of Recursive Functions and Effective Computability, MIT Press, ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
• Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
• Robert I. Soare (1987), Recursively Enumerable Sets and Degrees, Springer-Verlag, ISBN 0-387-15299-7

ca:Entscheidungsproblem de:Entscheidungsproblem es:Problema de decisión fr:Problème de la décision ko:판정 문제 he:בעיית הכרעה hr:Problem odluke kn:ನಿರ್ಣಯ ಪ್ರಶ್ನೆ ja:決定問題 pl:Problem decyzyjny (teoria obliczeń) pt:Problema de decisão sr:Проблем одлучивања zh:決定性問題

Notes

It should be noted that a decision problem is always a set of related problems which is in some sense large enough. A single problem P is always trivially decidable by assigning the constant function f(P)≡0 or f(P)≡1 to it.

Nearly every problem can be cast as a decision problem by using reductions, often with little effect on the amount of time or space needed to solve the problem. Many traditional hard problems have been cast as decision problems because this makes them easier to study and to solve, and proving that these problems are hard suffices to show that more complex problems are hard as well.

Equivalence to computation problems

Every decision problem is reducible to a computation problem in the following way. Every class of yes-or-no questions is reducible to the predicate form "Is $P(x_{1},...,x_{n})$ true?." For example, the above example is reducible to "Is $P(x,y)$ true?." This predicate form is reducible to the representing function $f(x_{1},...,x_{n})=\left\{{\begin{matrix}1,&{\mbox{if }}P(x_{1},...,x_{n}){\mbox{ is true}}\\0,&{\mbox{if }}P(x_{1},...,x_{n}){\mbox{ is false}}\end{matrix}}\right.$

So deciding whether $P(x_{1},...,x_{n})$ is true is equivalent to computing the value for $f(x_{1},...,x_{n})$.

References

• N. J. Cutland, Computability: An Introduction to Recursive Function Theory, Cambridge University Press, ISBN 0521294657.

An introductory mathematical textbook on computability theory with accessible treatment of the technical underpinnings of and many examples of solvable and unsolvable decision problems.

• George S. Boolos, John P. Burgess, and Richard C. Jeffrey, Computability and Logic, fourth edition, Cambridge University Press, ISBN 0521007585.

A introductrory textbook for philosophically-minded readers on computability and logic.

• Martin Davis (editor), The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Dover Publications, ISBN 0486432289.

A classic collection of fundamental contributions to computability theory.

• Martin Davis, Engines of Logic: Mathematicians and the Origin of the Computer, second edition, W. W. Norton and Company, ISBN 0393322297.

A collection of biographical sketches tracing the development of the computer.

Biographical References

• Andrew Hodges, Alan Turing: The Enigma, Walker and Company.

Chapter 2, "The Spirit of Truth," discusses the some of the background that led to Turing's work on decision problems.

Credits

New World Encyclopedia writers and editors rewrote and completed the Wikipedia article in accordance with New World Encyclopedia standards. This article abides by terms of the Creative Commons CC-by-sa 3.0 License (CC-by-sa), which may be used and disseminated with proper attribution. Credit is due under the terms of this license that can reference both the New World Encyclopedia contributors and the selfless volunteer contributors of the Wikimedia Foundation. To cite this article click here for a list of acceptable citing formats.The history of earlier contributions by wikipedians is accessible to researchers here:

• decision_problem  ^history
• Recursion_theory  ^history

The history of this article since it was imported to New World Encyclopedia:

• History of "Decision problem"

Note: Some restrictions may apply to use of individual images which are separately licensed.