Decision problem

An example of a decision problem is deciding with the help of an algorithm whether a given natural number is prime.

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 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.

Therefore, the algorithm of a decision problem is to compute the characteristic function of a subset of the natural numbers.

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.

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.

Optimization problems themselves are still of interest in computability theory, as well as in fields such as operations research.