Decision problem

In

A decision procedure for a decision problem is an algorithmic method that answers the yes-no question on all inputs, and a decision problem is called decidable if there is a decision procedure for it. For example, the decision problem "given two numbers x and y, does x evenly divide y?" is decidable since there is a decision procedure called long division that gives the steps for determining whether x evenly divides y and the correct answer, YES or NO, accordingly. Some of the most important problems in mathematics are undecidable, e.g. the halting problem.

The field of computational complexity theory categorizes decidable decision problems by how difficult they are to solve. "Difficult", in this sense, is described in terms of the

A decision problem is the formal language of all inputs for which the output (the answer to the yes-no question on a given input) is YES.^{[notes 1]}

• These inputs can be natural numbers, but can also be values of some other kind, like binary
  alphabet
  .

• For example, if every input can be encoded by the alphabet ${\displaystyle \{0,1\}}$, then a decision problem is a subset ${\displaystyle L\subseteq \{0,1\}^{*}}$.^{[notes 1]}

• For another example, 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 decision procedure 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. Although much more efficient procedures of

• A decision problem is decidable or effectively solvable if the set of inputs for which the answer is YES is a
  recursive set.^{[notes 2]}
• A decision problem is partially decidable, semidecidable, solvable, or provable if the set of inputs for which the answer is YES is a
  recursively enumerable set
  .

Problems that are not decidable are undecidable, which means it is not possible to create an algorithm (efficient or not) that solves them. The halting problem is an important undecidable decision problem; for more examples, see list of undecidable problems.

Decision problems can be ordered according to

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

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

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.

• ALL (complexity)
• Computational problem
• Counting problem (complexity)
• logical theory
  .
• Formal language
• Search problem
• Word problem (mathematics)