Complexity theory: различия между версиями

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

A problem is assigned to the ''' <math>\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>\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>\mathcal P</math>-problem.

The class of <math>\mathcal P</math>-problems is a subset of the class of <math>\mathcal {NP}</math>-problems, but there also exist problems which are not <math>\mathcal {NP}</math>.

The ''' <math>\mathcal P</math> versus <math>\mathcal {NP}</math> problem''' is the determination of whether all <math>\mathcal {NP}</math> problems are actually <math>\mathcal P</math>-problems.

If <math>\mathcal P\neq\mathcal {NP}</math>, then the solution of <math>\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>\,C</math> is said to be ''' <math>\mathcal {NP}</math>-hard''' if every problem from <math>\mathcal {NP}</math> is reducible to <math>\,C</math> in polynomial time.

A problem which is both <math>\mathcal {NP}</math> and <math>\mathcal {NP}</math>-hard is called an ''' <math>\mathcal {NP}</math>-complete problem'''. Examples of <math>\mathcal {NP}</math>-complete problems include the ''[[Hamiltonian cycle]], [[traveling salesman problem|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|<math>\mathcal {NP}</math>-complete problem]] is a <math>\mathcal P</math>-problem then <math>\mathcal P\,=\mathcal {NP}</math> and, vice versa, if some problem from <math>\mathcal {NP}</math>-problem class is ''intractable'' then all <math>\mathcal {NP}</math>-complete problems are also intractable.

 

 

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