Complexity theory

Complexity theory — теория сложности.

The theory of classifying problems based on how difficult they are to solve. A problem is assigned to the [math]\displaystyle{ \mathcal P }[/math]-problem (polynomial-time) class if the number of steps needed to solve it is bounded by some power of the problem's size. A problem is assigned to the [math]\displaystyle{ \mathcal {NP} }[/math]-problem (nondeterministic polynomial-time) class if if it is solvable in polynomial time by a nondeterministic Turing machine.

A problem is called intractable if it is not a [math]\displaystyle{ \mathcal P }[/math]-problem. The class of [math]\displaystyle{ \mathcal P }[/math]-problems is a subset of the class of [math]\displaystyle{ \mathcal {NP} }[/math]-problems, but there also exist problems which are not [math]\displaystyle{ \mathcal {NP} }[/math].

The [math]\displaystyle{ \mathcal P }[/math] versus [math]\displaystyle{ \mathcal {NP} }[/math] problem is the determination of whether all [math]\displaystyle{ \mathcal {NP} }[/math] problems are actually [math]\displaystyle{ \mathcal P }[/math]-problems. If [math]\displaystyle{ \mathcal P\neq\mathcal {NP} }[/math], then the solution of [math]\displaystyle{ \mathcal {NP} }[/math]-problems requires (in the worst case) an exhaustive search while if they are, then asymptotically faster algorithms may exist. The answer is not currently known, but determination of the status of this question would have dramatic consequences for the potential speed with which many difficult and important problems could be solved.

A problem [math]\displaystyle{ \,C }[/math] is said to be [math]\displaystyle{ \mathcal {NP} }[/math]-hard if every problem from [math]\displaystyle{ \mathcal {NP} }[/math] is reducible to [math]\displaystyle{ \,C }[/math] in polynomial time. A problem which is both [math]\displaystyle{ \mathcal {NP} }[/math] and [math]\displaystyle{ \mathcal {NP} }[/math]-hard is called an [math]\displaystyle{ \mathcal {NP} }[/math]-complete problem. Examples of [math]\displaystyle{ \mathcal {NP} }[/math]-complete problems include the Hamiltonian cycle, traveling salesman problems, Hamiltonian path problem, subgraph isomorphism problem, clique problem, vertex cover problem, independent set problem, dominating set problem, graph coloring problem.

Thus, if some [math]\displaystyle{ \mathcal {NP} }[/math]-complete problem is a [math]\displaystyle{ \mathcal P }[/math]-problem then [math]\displaystyle{ \mathcal P\,=\mathcal {NP} }[/math] and, vice versa, if some problem from [math]\displaystyle{ \mathcal {NP} }[/math]-problem class is intractable then all [math]\displaystyle{ \mathcal {NP} }[/math]-complete problems are also intractable.

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.