In computability theory and computational complexity theory, a **decision problem** is a question in some formal system with a yes-or-no answer. For example, the problem "given two 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*. Computability theory is the branch of theoretical computer science that studies which problems are computationally solvable using different models of computation. ...
As a branch of the theory of computation in computer science, computational complexity theory describes the scalability of algorithms, and the inherent difficulty in providing scalable algorithms for specific computational problems. ...
In logic, mathematics, and computer science, a formal system is a formal grammar used for modelling purposes. ...
Decision problems are closely related to function problems, which can have answers that are more complex than a simple 'yes' or 'no'. A corresponding function problem is "given two numbers *x* and *y*, what is *x* divided by *y*?". They are also related to optimization problems, which are concerned with finding the *best* answer to a particular problem. In computational complexity theory, a function problem is a problem other than a decision problem, that is, a problem requiring a more complex answer than just YES or NO. Notable examples include the traveling salesman problem which asks for the route taken by the salesman, and the integer factorization problem...
In computer science, an optimization problem is the problem to find among all feasible solutions for some problem the best one. ...
Methods used to solve decision problems are called *decision procedures* or algorithms. An algorithm for this decision problem would explain how to determine whether *x* evenly divides *y*, given *x* and *y*. A decision problem which can be solved by some algorithm is called **decidable**. In mathematics, computing, linguistics, and related disciplines, an algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task which, given an initial state, will terminate in a defined end-state. ...
The field of computational complexity 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. In computational complexity theory, a computational resource is a resource used by some computational model in the solution of computational problems. ...
Recursion theory, or computability theory, is a branch of mathematical logic dealing with generalizations of the notion of computable function, and with related notions such as Turing degrees and effective descriptive set theory. ...
In computability theory, the Turing degree of a subset of the natural numbers, , is the equivalence class of all subsets of equivalent to under Turing reducibility. ...
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. In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. ...
## 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. In mathematics, logic, and computer science, a formal language is a set of finite-length words (i. ...
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. This article or section may be confusing or unclear for some readers, and should be edited to rectify this. ...
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**. In computability theory a countable set is called recursive, computable or decidable if we can construct an algorithm which terminates after a finite amount of time and decides whether or not a given element belongs to the set. ...
In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable or provable if: There is an algorithm that, when given an input number, eventually halts if and only if the input is an element of S. Or, equivalently, There is...
## 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. A primality test is an algorithm for determining whether an input number is prime. ...
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. In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input. ...
In computability theory, an undecidable problem is a problem whose language is not a recursively enumerable set. ...
Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ...
In mathematics and related technical fields, a mathematical object is complete if nothing needs to be added to it. ...
To meet Wikipedias quality standards, this article or section may require cleanup. ...
In computational complexity theory, SL (Symmetric Logspace) is the complexity class of problems log-space reducible to USTCON, which is the problem of determining whether there exists a path between two vertices in an undirected graph, otherwise described as the problem of determining whether two vertices are in the same...
## 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. The Entscheidungsproblem (German for decision problem) is the challenge in symbolic logic to find a general algorithm which decides for given first-order statements whether they are universally valid or not. ...
David Hilbert (January 23, 1862, Wehlau, East Prussia â€“ February 14, 1943, GÃ¶ttingen, Germany) was a German mathematician, recognized as one of the most influential mathematicians of the 19th and early 20th centuries. ...
The ignorabimus, short for the Latin tag ignoramus et ignorabimus meaning we do not know and will not know, stood for a pessimistic (in one sense) position on the limits on scientific knowledge, in the thought of the nineteenth century. ...
David Hilbert (January 23, 1862, Wehlau, East Prussia â€“ February 14, 1943, GÃ¶ttingen, Germany) was a German mathematician, recognized as one of the most influential mathematicians of the 19th and early 20th centuries. ...
In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input. ...
## 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. In computational complexity theory, a function problem is a problem other than a decision problem, that is, a problem requiring a more complex answer than just YES or NO. Notable examples include the traveling salesman problem which asks for the route taken by the salesman, and the integer factorization 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 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. In the mathematical subfield of set theory, the indicator function, or characteristic function, is a function defined on a set X which is used to indicate membership of an element in a subset A of X. Remark. ...
## 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 |