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

Glk (обсуждение | вклад) (Новая страница: «'''Complexity theory''' --- теория сложности. The theory of classifying problems based on how difficult they are to solve. A problem is assigned to t…») |
KEV (обсуждение | вклад) |
||

Строка 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 ''' | + | 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 ''' | + | 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 | + | 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 | ||

− | The ''' | + | 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 | + | 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 ''' | + | 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 | + | 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 | ||

− | 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 | + | 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 | + | |

+ | ==Литература== | ||

+ | |||

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

## Текущая версия на 14:17, 12 ноября 2014

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

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

The ** versus problem** is the determination of whether all problems are actually -problems.
If , then the solution of -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 is said to be ** -hard** if every problem from is reducible to in polynomial time.
A problem which is both and -hard is called an ** -complete problem**. Examples of -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 -complete problem is a -problem then and, vice versa, if some problem from -problem class is *intractable* then all -complete problems are also intractable.

## Литература

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