Difference between revisions of "Decision problem" - New World Encyclopedia

Revision as of 01:59, 11 September 2007

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 tell us how to determine whether x evenly divides y, given x and y for every value of "x" and "y".

When a decision problem has some decision procedure, such as in this example, the problem is said to be decidable and otherwise undecidable. The intuitive concept of effectiveness, which the concept of decision procedures invokes, has been considered as the formal concept, computability, (and other equivalent concepts) by Church-Turing thesis.

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. The problem "given two natural numbers x and y, does x evenly divide y?", and the problem "In a sequence x of English alphabets, is there any occurrence of "aa"?" are examples of decision problems.

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 the decision problem "given two numbers x and y, does x evenly divide y?", one example of decision procedures is taught to all school children and is called "long division."

A decision problem is called decidable, if there is a decision procedure; otherwise, it is called undecidable. The intuitive notion of effectiveness procedure, which the notion of the decision procedure invokes, has been explained by the formal concept, computable functions (a function that Turing machine can compute) and other equivalent concepts such as recursive sets.

Since decision problems can be given yes-or-no answers, a decision problem can be considered as the set of inputs for which the problem returns yes. As such, a decision problem can be further considered as a set of natural numbers by associating with natural numbers inputs in the specified sets of a given decision problem in some systematic way (often by using Gödel numbering). Then formally the decision procedure of a given decision problem can be considered in the following way. Let A be a subset of natural numbers. The decision procedure of the decision problem A is a computable function f such that, for every natural number x, f(x)=1 if x is in A; f(x)=0 if x is not in A. (Here the value 1 is considered as the answer "yes" and the value 0, as "no".)

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 decidable then the function problem would be as well.

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.

Thus for instance

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.

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:決定性問題

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:

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.

@@ Line 4: / Line 4: @@
 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'''.
+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 tell us how to determine whether ''x'' evenly divides ''y'', given ''x'' and ''y'' for every value of "x" and "y".
+When a decision problem has some decision procedure, such as in this example, the problem is said to be '''decidable''' and otherwise '''undecidable'''. The intuitive concept of effectiveness, which the concept of decision procedures invokes, has been considered as the formal concept, [[Alonzo Church|computability]],  (and other equivalent concepts) by [[Alonzo Church|Church-Turing thesis]].
 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.
@@ Line 10: / Line 12: @@
 ==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.
+A '''decision problem''' is any arbitrary yes-or-no question on specified sets of inputs.  The problem "given two natural numbers ''x'' and ''y'', does ''x'' evenly divide ''y''?", and the problem "In a sequence ''x'' of English alphabets, is there any occurrence of  "aa"?" are examples of decision problems.
-Formally, a '''decision problem''' is a subset ''A'' of the natural numbers.  By using [[Gödel number]]s, 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 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 the decision problem "given two numbers ''x'' and ''y'', does ''x'' evenly divide ''y''?", one example of decision procedures is taught to all school children and is called "long division."
-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'''.
+A decision problem is called '''decidable''', if there is a decision procedure; otherwise, it is called '''undecidable'''. The intuitive notion of effectiveness procedure, which the notion of the decision procedure invokes, has been explained by the formal concept, [[Alonzo Church|computable functions]] (a function that [[Alan Turing|Turing machine]] can compute)  and other equivalent concepts such as recursive sets.
-==Definition==
+Since decision problems can be given yes-or-no answers, a decision problem can be considered as the set of inputs for which the problem returns ''yes''. As such, a decision problem can be further considered as a set of natural numbers by associating with natural numbers inputs in the specified sets of a given decision problem in some systematic way (often by using Gödel numbering). Then formally the decision procedure of a given decision problem can be considered in the following way. Let ''A'' be a subset of natural numbers. The decision procedure of the decision problem ''A'' is a computable function ''f'' such that, for every natural number ''x'', ''f''(''x'')=1 if ''x'' is in ''A''; ''f''(''x'')=0 if ''x'' is not in ''A''. (Here the value 1 is considered as the answer "yes" and the value 0, as "no".)
-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]].
+==Equivalence with function problems==<!— This section is linked from [[Decision problem]] —>
-Formally, a '''decision problem''' is a [[countable set|countable]] [[set]] ''S'' and a [[function_(mathematics)|function]]
+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.
-:<math>f:S \to \lbrace0, 1\rbrace</math>.
-Let ''A'' be the [[preimage]] of ''f'' for 1.
-:<math>A := \lbrace s \in S | f(s) = 1 \rbrace = f^{-1}(\lbrace 1 \rbrace)</math>
-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 function]]s:
+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 decidable then the function problem would be as well.
-If ''f'' is a [[total function|total]] computable function, the problem is called '''computable'''. If ''f'' is only a [[partial function|partial]] computable function, the problem is called '''partially computable'''. Otherwise, the problem is called '''uncomputable'''.
+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.
+Thus for instance
 ==Examples==
@@ Line 39: / Line 36: @@
 Important undecidable decision problems include the [[halting problem]]; for more, see [[list of undecidable problems]]. In [[complexity theory (computation)|computational complexity]], decision problems which are [[complete problem|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 reachability problem|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==<!-- This section is linked from [[Decision problem]] —>
-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''<sup>''x''</sup> has this property.
-Every decision problem can be converted into the function problem of computing the [[indicator function|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 ==
@@ Line 80: / Line 65: @@
 [[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'')&equiv;0 or ''f''(''P'')&equiv;1 to it.
-Nearly every problem can be cast as a decision problem by using [[reduction (complexity)|reduction]]s, 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 <math>P(x_1,...,x_n)</math> true?." For example, the above example is reducible to "Is <math>P(x,y)</math> true?." This predicate form is reducible to the [[representing function]] <math>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.</math>
-So deciding whether <math>P(x_1,...,x_n)</math> is true is equivalent to computing the value for <math>f(x_1,...,x_n)</math>.
-== 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.
-[[Category:Logic]]
-[[Category:Theory of computation]]
-[[Category:Computational problems]]
-[[Category:Philosophy and religion]]
 {{Credits|decision_problem|48562268|Recursion_theory|154814257}}