Difference between revisions of "Decision problem" - New World Encyclopedia
| Line 18: | Line 18: | ||
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. | 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. | ||
| − | 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".) | + | 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".) The function here is called a ''characteristic function'' of the decision problem. |
==Equivalence with function problems==<!-- This section is linked from [[Decision problem]] —> | ==Equivalence with function problems==<!-- This section is linked from [[Decision problem]] —> | ||
| − | A | + | 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. An example is the problem "Given two numbers x and y, what is x divided by y?". |
| − | 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 | + | 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 that yields the answer of the function problem is computable. |
| − | Every decision problem can be converted into the function problem of computing the characteristic function of the set associated to the decision problem. | + | 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 | + | Thus for instance, the decision problem "given two numbers x and y, does x evenly divide y?" and the function problem "given two numbers x and y, what is x divided by y?" are equivalent in the sense that they can be converted into each other in the above way. |
==Examples== | ==Examples== | ||
| + | Examples of ''decidable'' decision problems (considered as a subset of natural numbers) are: | ||
| + | *The problem whether a given number is odd (or even). | ||
| + | *The problem whether a given number is a prime number. | ||
| + | *The problem whether a given given number is in a specified finite or cofinite subset of natural numbers. | ||
| − | + | Examples of ''undecidable'' decision problems are: | |
| − | + | * The halting problem (whether a specified [[Alan Turing|Turing machine]] halts or runs forever). | |
| − | + | * The busy beaver problem (determining the length of the longest halting computation among [[Alan Turing|Turing machines]] of a specified size). | |
| − | + | * Rice's theorem states that for all non-trivial properties of partial functions, it is undecidable whether a machine computes a partial function with that property. | |
== References == | == References == | ||
Revision as of 02:14, 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".) The function here is called a characteristic function of the decision problem.
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. An example is the problem "Given two numbers x and y, what is x divided by y?".
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 that yields the answer of the function problem is computable.
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, the decision problem "given two numbers x and y, does x evenly divide y?" and the function problem "given two numbers x and y, what is x divided by y?" are equivalent in the sense that they can be converted into each other in the above way.
Examples
Examples of decidable decision problems (considered as a subset of natural numbers) are:
- The problem whether a given number is odd (or even).
- The problem whether a given number is a prime number.
- The problem whether a given given number is in a specified finite or cofinite subset of natural numbers.
Examples of undecidable decision problems are:
- The halting problem (whether a specified Turing machine halts or runs forever).
- The busy beaver problem (determining the length of the longest halting computation among Turing machines of a specified size).
- Rice's theorem states that for all non-trivial properties of partial functions, it is undecidable whether a machine computes a partial function with that property.
ReferencesISBN 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:
Note: Some restrictions may apply to use of individual images which are separately licensed.
