Complexity theory

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

The theory of classifying problems based on how difficult they are to solve. A problem is assigned to the P-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 NP-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 P-problem. The class of P-problems is a subset of the class of NP-problems, but there also exist problems which are not NP.

The P versus NP problem is the determination of whether all NP problems are actually P-problems. If P[math]\displaystyle{ \neq }[/math]NP, then the solution of NP-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 NP-hard if every problem from NP is reducible to [math]\displaystyle{ C }[/math] in polynomial time. A problem which is both NP and NP-hard is called an NP-complete problem. Examples of NP-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 NP-complete problem is a P-problem then P=NP and,vice versa, if some problem from NP-problem class is intractable then all NP-complete problems are also intractable.