Incomputability theory andcomputational complexity theory, adecision problem is acomputational problem that can be posed as ayes–no question on aset of input values. An example of a decision problem is deciding whether a given natural number isprime. Another example is the problem, "given two numbersx andy, doesx evenly dividey?"
Adecision procedure for a decision problem is analgorithmic method that answers the yes-no question on all inputs, and a decision problem is calleddecidable if there is a decision procedure for it. For example, the decision problem "given two numbersx andy, doesx evenly dividey?" is decidable since there is a decision procedure calledlong division that gives the steps for determining whetherx evenly dividesy and the correct answer,YES orNO, accordingly. Some of the most important problems in mathematics areundecidable, e.g. thehalting problem.
The field of computational complexity theory categorizesdecidable decision problems by how difficult they are to solve. "Difficult", in this sense, is described in terms of thecomputational resources needed by the most efficient algorithm for a certain problem. On the other hand, the field ofrecursion theory categorizesundecidable decision problems byTuring degree, which is a measure of the noncomputability inherent in any solution.
Adecision problem is theformal language of all inputs for which the output (the answer to the yes-no question on a given input) isYES.[notes 1]
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 procedures ofprimality testing are known, the existence of any effective procedure is enough to establish decidability.
Problems that are not decidable areundecidable, which means it is not possible to create an algorithm (efficient or not) that solves them. Thehalting problem is an important undecidable decision problem; for more examples, seelist of undecidable problems.
Decision problems can be ordered according tomany-one reducibility and related to feasible reductions such aspolynomial-time reductions. A decision problemP is said to becomplete for a set of decision problemsS ifP is a member ofS and every problem inS can be reduced toP. Complete decision problems are used incomputational complexity theory to characterizecomplexity classes of decision problems. For example, theBoolean satisfiability problem is complete for the classNP of decision problems under polynomial-time reducibility.
Decision problems are closely related tofunction problems, which can have answers that are more complex than a simpleYES orNO. A corresponding function problem is "given two numbersx andy, what isx divided byy?".
Afunction problem consists of apartial functionf; the informal "problem" is to compute the values off 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 functionf is the set of pairs (x,y) such thatf(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 inpolynomial time (in which case running time is computed as a function ofx alone). The functionf(x) = 2x has this property.
Every decision problem can be converted into the function problem of computing thecharacteristic 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 anNP-complete problem and itsco-NP-completecomplement is exactly the same even though the underlying decision problems may not be considered equivalent in some typical models of computation.
Unlike decision problems, for which there is only one correct answer for each input, optimization problems are concerned with finding thebest answer to a particular input. Optimization problems arise naturally in many applications, such as thetraveling salesman problem and many questions inlinear programming.
Function and optimization problems are often transformed into decision problems by considering the question of whether the output isequal to orless 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 eachN, to decide whether the graph has any tour with weight less thanN. 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 asoperations research.
| General | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Theorems (list) and paradoxes | |||||||||
| Logics |
| ||||||||
| Set theory |
| ||||||||
| Formal systems (list), language and syntax |
| ||||||||
| Proof theory | |||||||||
| Model theory | |||||||||
| Computability theory | |||||||||
| Related | |||||||||
Authority control databases: National |
|---|
