Decision problem

Материал из WikiGrapp
Перейти к:навигация, поиск

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 A is called decidable or effectively solvable if A 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 A.

A problem is called partially decidable, semidecidable, solvable, or provable if A 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 A.

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