Decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whether a given natural number is prime. Another is the problem "given two numbers x and y, does x evenly divide y?". The answer is either 'yes' or 'no' depending upon the values of x and y. A method for solving a decision problem, given in the form of an algorithm, is called a decision procedure for that problem. A decision procedure for the decision problem "given two numbers x and y, does x evenly divide y?" would give the steps for determining whether x evenly divides y. One such algorithm is long division. If the remainder is zero the answer is 'yes', otherwise it is 'no'. A decision problem which can be solved by an algorithm is called decidable.
Decision problems typically appear in mathematical questions of decidability, that is, the question of the existence of an effective method to determine the existence of some object or its membership in a set; some of the most important problems in mathematics are undecidable.
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
Definition
A decision problem is a yes-or-no question on an infinite set of inputs. It is traditional to define the decision problem as the set of possible inputs together with the set of inputs for which the answer is yes.[1]
These inputs can be natural numbers, but can also be values of some other kind, like binary
Using an encoding such as Gödel numbering, any string can be encoded as a natural number, via which a decision problem can be defined as a subset of the natural numbers. Therefore, the algorithm of a decision problem is to compute the characteristic function of a subset of the natural numbers.
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 nontrivial factor. Although much more efficient methods of
Decidability
A decision problem is decidable or effectively solvable if the set of inputs (or natural numbers) for which the answer is yes is a
The halting problem is an important undecidable decision problem; for more examples, see list of undecidable problems.
Complete problems
Decision problems can be ordered according to
Function problems
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?".
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
Every decision problem can be converted into the function problem of computing the
Optimization problems
Unlike decision problems, for which there is only one correct answer for each input, optimization problems are concerned with finding the best answer to a particular input. Optimization problems arise naturally in many applications, such as the
Function and optimization problems are often transformed into decision problems by considering the question of whether the output is equal to or less than or equal to a given value. This allows the complexity of the corresponding decision problem to be studied; and in many cases the original function or optimization problem can be solved by solving its corresponding decision problem. For example, in the traveling salesman problem, the optimization problem is to produce a tour with minimal weight. The associated decision problem is: for each N, to decide whether the graph has any tour with weight less than N. By repeatedly answering the decision problem, it is possible to find the minimal weight of a tour.
Because the theory of decision problems is very well developed, research in complexity theory has typically focused on decision problems. Optimization problems themselves are still of interest in computability theory, as well as in fields such as operations research.
See also
- ALL (complexity)
- Computational problem
- logical theory.
- Search problem
- Counting problem (complexity)
- Word problem (mathematics)
References
- Kozen, D.C. (2012). Automata and Computability. Springer. ISBN 978-1-4612-1844-9.
- Hartley, Rogers Jr (1987). The Theory of Recursive Functions and Effective Computability. MIT Press. ISBN 978-0-262-68052-3.
- ISBN 978-0-357-67058-3.
- Soare, Robert I. (1987). Recursively Enumerable Sets and Degrees. Springer. ISBN 0-387-15299-7.
- ISBN 978-3-540-74104-6.
- Bradley, Aaron; ISBN 978-3-540-74112-1.
- ^ "CS254: Computational Complexity: Lecture 2" (PDF). Archived (PDF) from the original on 2015-10-10.