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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Complexity theory''' --- теория сложности. The theory of classifying problems based on how difficult they are to solve. A problem is assigned to t…»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Complexity theory''' --- теория сложности.
'''Complexity theory''' — ''[[теория сложности]].''


The theory of classifying problems based on how difficult they are to solve.
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
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 ''' ''NP''-problem (nondeterministic polynomial-time) class''' if if it is solvable in polynomial time by a ''nondeterministic Turing machine''.
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 P-problem.
A problem is called '''intractable''' if it is not a <math>\mathcal P</math>-problem.
The class of ''P''-problems is a subset of the class of ''NP''-problems,
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>.
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.
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 ''P''<math>\neq</math>''NP'', then the solution of ''NP''-problems requires (in the worst case) an ''exhaustive search''
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.
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 ''' ''NP''-hard''' if every problem from ''NP'' is reducible to <math>C</math> in polynomial time.
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 ''NP'' and ''NP''-hard is called an ''' ''NP''-complete problem'''.
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]].''
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''
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.
then all ''NP''-complete problems are also intractable.
 
==Литература==
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.

Текущая версия от 10:48, 24 октября 2018

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.