Decision problem
|
|
In logic, a decision problem is determining whether or not there exists a decision procedure or algorithm for a class S of questions requiring a Boolean value (i.e., a true or false, or yes or no). These are also known as yes-or-no questions. For example, the decision problem for the class of questions "Does x divide y without remainder?" is decidable because there exists a mechanical procedure, namely long division, which allows us to determine for any x and any y whether the answer for "Does x divide y without remainder?" is yes or no.
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} 0, & \mbox{if }P(x_1,...,x_n)\mbox{ is true} \\ 1, & \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>.
Definition
A decision problem is a countable set S and a function
- <math>f:S \to \lbrace0, 1\rbrace<math>.
Let A be the preimage of f for 0.
- <math>A := \lbrace s \in S | f(s) = 0 \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 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.
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.
Examples
Important undecidable decision problems include the halting problem and Goodstein's theorem; 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.de:Entscheidungsproblem es:Problema de decisión fr:Problème de la décision he:בעיית הכרעה