Decision problem

Decision problem --- задача распознавания свойств.

A decision problem is one that asks only for a yes-or-no answer: Can this graph be 5-colored? Is there a set of 67 independent vertices?

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 strings of a formal language. Using some encoding, such as Godel numbers, 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 natural numbers.

A decision problem [math]\displaystyle{ A }[/math] is called decidable or effectively solvable if [math]\displaystyle{ A }[/math] is a recursive set, i.e. if there is an algorithm which terminates in a finite time and correctly decides whether or not a given number belongs to the set [math]\displaystyle{ A }[/math].

A problem is called partially decidable, semidecidable, solvable, or provable if [math]\displaystyle{ A }[/math] is a recursively enumerable set, i.e. there is an algorithm that, when given an input number, eventually halts if and only if the input is an element of [math]\displaystyle{ A }[/math].

Partially decidable problems and any other problems that are not decidable are called undecidable.