Decision problem

In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. Problems with more complex answers are called function problems. The problem itself is distinct from the methods used to solve it, called decision procedures or algorithms. A decision problem which can be solved by some algorithm is called decidable.

One example of a decision problem is "given two numbers x and y, does x evenly divide y?". This is a yes-or-no question, and its answer depends on the values of x and y. An algorithm for this decision problem would tell how to determine whether x evenly divides y, given x and y.

Decision problems are closely related to function problems, which are allowed to have any answers, not just yes-or-no answers. For example, one function problem is "given two numbers x and y, what is x divided by y?". However, research in computability theory has typically focused on decision problems. As explained in the section Equivalence with function problems below, there is no loss of generality.

The field of computational complexity categorizes decidable decision problems based on how difficult they are to solve, in terms of the computational resources needed by the most efficient algorithms for that decision problem. The field of recursion theory categorizes undecidable decision problems by Turing degree, a measure of the noncomputability inherent in any solution to the problem.

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 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. Otherwise, the problem is called undecidable.

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 nontrival 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

• 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