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.

For example, we might have a decision problem "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 us how, given x and y, we can determine whether x evenly divides y.

Decision problems are somewhat less intuitively useful than function problems, which are allowed to have any answers, not just yes-or-no answers. For example, a function problem might be "given two numbers x and y, what is x divided by y?." However, computational complexity theory has typically found it easier to study decision problems. In complexity theory, we attempt to categorize decision problems based on how "difficult" they are, in terms of the computational resources needed by the most efficient algorithms for that decision 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 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.

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; 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 as to whether that assertion was true" (Hodges, p. 91). Hilbert believed that "in mathematics there is no ignorabimus' (Hodges, p. 91ff) meaning 'we do not know and will not know'. See David Hilbert and Halting Problem for more.

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
ISBN links support NWE through referral fees

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:

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.