Decision problem
Encyclopedia
In computability theory
and computational complexity theory
, a decision problem is a question in some formal system
with a yes-or-no answer, depending on the values of some input parameters. 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.
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; many of the important problems in mathematics are undecidable
.
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 problem
s, which are concerned with finding the best answer to a particular problem.
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, given x and y. One such algorithm is long division
, taught to many school children. If the remainder is zero the answer produced is 'yes', otherwise it is 'no'. A decision problem which can be solved by an algorithm, such as this example, is called decidable.
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 resource
s 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.
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.
These inputs can be natural numbers, but also other values of some other kind, such as string
s of a formal language
. Using some encoding, such as Gödel numberings, the strings can be encoded as natural numbers. Thus, a decision problem informally phrased in terms of a formal language is also equivalent to a set of natural numbers. To keep the formal definition simple, it is phrased in terms of subsets of the natural numbers.
Formally, a decision problem is a subset of the natural numbers. The corresponding informal problem is that of deciding whether a given number is in the set.
. A problem is called partially decidable, semidecidable, solvable, or provable if A is a recursively enumerable set
. Partially decidable problems and any other problems that are not decidable are called undecidable.
The halting problem
is an important undecidable decision problem; for more examples, see list of undecidable problems.
and related feasible reductions such as Polynomial-time reduction
s. A decision problem P is said to be complete for a set of decision problems S if P is a member of S and every problem in S can be reduced to P. Complete decision problems are used in computational complexity to characterize complexity classes of decision problems. For example, the Boolean satisfiability problem
is complete for the class NP
of decision problems under polynomial-time reducibility.
, 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.
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) = 2x 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.
techniques based on the DPLL algorithm
. Conjunctive formulas over linear real or rational arithmetic can be decided using the Simplex algorithm
, formulas in linear integer arithmetic (Presburger arithmetic
) can be decided using Cooper's algorithm or William Pugh
's Omega test. Formulas with negations, conjunctions and disjunctions combine the difficulties of satisfiability testing with that of decision of conjunctions; they are generally decided nowadays using SMT-solving
technique, which combine SAT-solving with decision procedures for conjunctions and propagation techniques. Real polynomial arithmetic, also known as the theory of real closed field
s, is decidable, for instance using the Cylindrical algebraic decomposition
; unfortunately the complexity of that algorithm is excessive for most practical uses.
A leading scientific conference in this field is CAV
.
Computability theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
and computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, a decision problem is a question in some formal system
Formal system
In formal logic, a formal system consists of a formal language and a set of inference rules, used to derive an expression from one or more other premises that are antecedently supposed or derived . The axioms and rules may be called a deductive apparatus...
with a yes-or-no answer, depending on the values of some input parameters. 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.
Decision problems typically appear in mathematical questions of decidability
Decidability (logic)
In logic, the term decidable refers to the decision problem, the question of the existence of an effective method for determining membership in a set of formulas. Logical systems such as propositional logic are decidable if membership in their set of logically valid formulas can be effectively...
, that is, the question of the existence of an effective method
Effective method
In computability theory, an effective method is a procedure that reduces the solution of some class of problems to a series of rote steps which, if followed to the letter, and as far as may be necessary, is bound to:...
to determine the existence of some object or its membership in a set; many of the important problems in mathematics are undecidable
Undecidable problem
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer....
.
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 problem
Optimization problem
In mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. An optimization problem with discrete...
s, which are concerned with finding the best answer to a particular problem.
A method for solving a decision problem given in the form of an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
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, given x and y. One such algorithm is long division
Long division
In arithmetic, long division is a standard procedure suitable for dividing simple or complex multidigit numbers. It breaks down a division problem into a series of easier steps. As in all division problems, one number, called the dividend, is divided by another, called the divisor, producing a...
, taught to many school children. If the remainder is zero the answer produced is 'yes', otherwise it is 'no'. A decision problem which can be solved by an algorithm, such as this example, is called decidable.
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 resource
Computational resource
In computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems....
s needed by the most efficient algorithm for a certain problem. The field of recursion theory
Recursion theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
, meanwhile, categorizes undecidable decision problems by Turing degree
Turing degree
In computer science and mathematical logic the Turing degree or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set...
, which is a measure of the noncomputability inherent in any solution.
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.
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 equivalently as: the set of inputs for which the problem returns yes.These inputs can be natural numbers, but also other values of some other kind, such as string
String (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
s of a formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
. Using some encoding, such as Gödel numberings, the strings can be encoded as natural numbers. Thus, a decision problem informally phrased in terms of a formal language is also equivalent to a set of natural numbers. To keep the formal definition simple, it is phrased in terms of subsets of the natural numbers.
Formally, a decision problem is a subset of the natural numbers. The corresponding informal problem is that of deciding whether a given number is in the set.
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 primality testing are known, the existence of any effective method is enough to establish decidability.Decidability
A decision problem A is called decidable or effectively solvable if A is a recursive setRecursive set
In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which terminates after a finite amount of time and correctly decides whether or not a given number belongs to the set....
. A problem is called partially decidable, semidecidable, solvable, or provable if A is a recursively enumerable set
Recursively enumerable set
In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if:...
. Partially decidable problems and any other problems that are not decidable are called undecidable.
The halting problem
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
is an important undecidable decision problem; for more examples, see list of undecidable problems.
Complete problems
Decision problems can be ordered according to many-one reducibilityMany-one reduction
In computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. Reductions are thus used to measure the relative computational difficulty of two problems.Many-one...
and related feasible reductions such as Polynomial-time reduction
Polynomial-time reduction
In computational complexity theory a polynomial-time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time. If it is a many-one reduction, it is called a polynomial-time many-one reduction, polynomial transformation, or Karp reduction...
s. A decision problem P is said to be complete for a set of decision problems S if P is a member of S and every problem in S can be reduced to P. Complete decision problems are used in computational complexity to characterize complexity classes of decision problems. For example, the Boolean satisfiability problem
Boolean satisfiability problem
In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
is complete for the class NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
of decision problems under polynomial-time reducibility.
History
The EntscheidungsproblemEntscheidungsproblem
In mathematics, the is a challenge posed by David Hilbert in 1928. The asks for an algorithm that will take as input a description of a formal language and a mathematical statement in the language and produce as output either "True" or "False" according to whether the statement is true or false...
, German for "Decision-problem", is attributed to David Hilbert
David Hilbert
David Hilbert was a German mathematician. He is recognized as one of the most influential and universal mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many areas, including invariant theory and the axiomatization of...
: "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
Ignorabimus
The Latin maxim ignoramus et ignorabimus, meaning "we do not know and will not know", stood for a position on the limits of scientific knowledge, in the thought of the nineteenth century...
' (Hodges, p. 91ff) meaning 'we will not know'. See David Hilbert
David Hilbert
David Hilbert was a German mathematician. He is recognized as one of the most influential and universal mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many areas, including invariant theory and the axiomatization of...
and Halting Problem
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
for more.
Equivalence with function problems
A function problemFunction problem
In computational complexity theory, a function problem is a computational problem where a single output is expected for every input, but the output is more complex than that of a decision problem, that is, it isn't just YES or NO...
consists of a partial function
Partial function
In mathematics, a partial function from X to Y is a function ƒ: X' → Y, where X' is a subset of X. It generalizes the concept of a function by not forcing f to map every element of X to an element of Y . If X' = X, then ƒ is called a total function and is equivalent to a 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) = 2x 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
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
problem and its co-NP-complete
Co-NP-complete
In complexity theory, computational problems that are co-NP-complete are those that are the hardest problems in co-NP, in the sense that they are the ones most likely not to be in P...
complement
Complement (complexity)
In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers. Equivalently, if we define decision problems as sets of finite strings, then the complement of this set over some fixed domain is its complement...
is exactly the same even though the underlying decision problems may not be considered equivalent in some typical models of computation.
Practical decision
Having practical decision procedures for classes of logical formulas is of considerable interest for program verification and circuit verification. Pure Boolean logical formulas are usually decided using SAT-solvingBoolean satisfiability problem
In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
techniques based on the DPLL algorithm
DPLL algorithm
The Davis–Putnam–Logemann–Loveland algorithm is a complete, backtracking-based algorithm for deciding the satisfiability of propositional logic formulae in conjunctive normal form, i.e. for solving the CNF-SAT problem....
. Conjunctive formulas over linear real or rational arithmetic can be decided using the Simplex algorithm
Simplex algorithm
In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the twentieth century....
, formulas in linear integer arithmetic (Presburger arithmetic
Presburger arithmetic
Presburger arithmetic is the first-order theory of the natural numbers with addition, named in honor of Mojżesz Presburger, who introduced it in 1929. The signature of Presburger arithmetic contains only the addition operation and equality, omitting the multiplication operation entirely...
) can be decided using Cooper's algorithm or William Pugh
William Pugh
William Pugh is the inventor of the skip list, the Omega test for deciding Presburger arithmetic, co-author of the static code analysis tool FindBugs, and was highly influential in the development of the current memory model of the Java language together with his PhD student Jeremy Manson.He is...
's Omega test. Formulas with negations, conjunctions and disjunctions combine the difficulties of satisfiability testing with that of decision of conjunctions; they are generally decided nowadays using SMT-solving
Satisfiability Modulo Theories
In computer science, the Satisfiability Modulo Theories problem is a decision problem for logical formulas with respect to combinations of background theories expressed in classical first-order logic with equality...
technique, which combine SAT-solving with decision procedures for conjunctions and propagation techniques. Real polynomial arithmetic, also known as the theory of real closed field
Real closed field
In mathematics, a real closed field is a field F that has the same first-order properties as the field of real numbers. Some examples are the field of real numbers, the field of real algebraic numbers, and the field of hyperreal numbers.-Definitions:...
s, is decidable, for instance using the Cylindrical algebraic decomposition
Cylindrical algebraic decomposition
Given a set of polynomials in Rn and a set S in Rn the Cylindrical algebraic decomposition algorithm finds a decomposition of S in to a number of cells such that for each cell each polynomial has constant sign.-References:...
; unfortunately the complexity of that algorithm is excessive for most practical uses.
A leading scientific conference in this field is CAV
Computer Aided Verification
Computer Aided Verification is an annual academic conference on the theory and practice of computer aided formal analysis of software and hardware systems. The conference consists of peer-reviewed research papers and system descriptions. The proceedings are published by Springer in the LNCS series...
.
See also
- ALL (complexity)ALL (complexity)In computability and complexity theory, ALL is the class of all decision problems.-Relations to other classes:ALL contains all complexity classes of decision problems, including RE and co-RE....
- Decidability (logic)Decidability (logic)In logic, the term decidable refers to the decision problem, the question of the existence of an effective method for determining membership in a set of formulas. Logical systems such as propositional logic are decidable if membership in their set of logically valid formulas can be effectively...
– for the problem of deciding whether a formula is a consequence of a logical theory. - yes-no questionYes-no questionIn linguistics, a yes–no question, formally known as a polar question, is a question whose expected answer is either "yes" or "no". Formally, they present an exclusive disjunction, a pair of alternatives of which only one is acceptable. In English, such questions can be formed in both positive...
- Optimization problemOptimization problemIn mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. An optimization problem with discrete...
- Search problemSearch problemIn computational complexity theory and computability theory, a search problem is a type of computational problem represented by a binary relation...
- Counting problem (complexity)
- Function problemFunction problemIn computational complexity theory, a function problem is a computational problem where a single output is expected for every input, but the output is more complex than that of a decision problem, that is, it isn't just YES or NO...
- Word problem (mathematics)Word problem (mathematics)In mathematics and computer science, a word problem for a set S with respect to a system of finite encodings of its elements is the algorithmic problem of deciding whether two given representatives represent the same element of the set...
Effective decision
- Daniel Kroening & Ofer Strichman, Decision procedures, Springer, ISBN 978-3-540-74104-6
- Aaron Bradley & Zohar MannaZohar MannaZohar Manna is a professor of computer science at Stanford University. He is the author of The Mathematical Theory of Computation , one of the first texts to provide extensive coverage of the mathematical concepts behind computer programming.With Amir Pnueli, he co-authored an unfinished trilogy...
, The calculus of computation, Springer, ISBN 978-3-540-74112-1