Теорема Кука: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Теорема Кука''' (''S.A.Cook, 1971'') - ''задача о выполнимости'' является ''<math>\cal NP</math>-...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Теорема Кука''' (''S.A.Cook, 1971'') - | '''Теорема Кука''' (''[[S.A.Cook, 1971]]'') - | ||
''задача о выполнимости'' является ''<math>\ | ''[[задача о выполнимости]]'' является ''[[NP-Полная задача|<math>\mathcal NP</math>-полной]]''. | ||
См. также ''Задача о вершинном покрытии, Задача о клике, Задача о неэквивалентности регулярных выражений, Задача о разбиении, Задача о точном покрытии 3-множествами, Задача о трехмерном сочетании, Классы <math>\ | ==См. также == | ||
''[[Задача о вершинном покрытии]], [[Задача о клике]], [[Задача о неэквивалентности регулярных выражений]], [[Задача о разбиении]], [[Задача о точном покрытии 3-множествами]], [[Задача о трехмерном сочетании]], [[Классы P и NP|Классы <math>\mathcal P</math> и <math>\mathcal NP</math>]], [[Метод локальной замены]], [[Метод построения компонент]], [[Метод сужения задачи]], [[Полиномиальная сводимость (трансформируемость)]], [[Труднорешаемая задача]].'' | |||
==Литература== | ==Литература== | ||
[Ахо-Хопкрофт-Ульман], | [Ахо-Хопкрофт-Ульман], | ||
Версия от 12:55, 4 февраля 2010
Теорема Кука (S.A.Cook, 1971) - задача о выполнимости является [math]\displaystyle{ \mathcal NP }[/math]-полной.
См. также
Задача о вершинном покрытии, Задача о клике, Задача о неэквивалентности регулярных выражений, Задача о разбиении, Задача о точном покрытии 3-множествами, Задача о трехмерном сочетании, Классы [math]\displaystyle{ \mathcal P }[/math] и [math]\displaystyle{ \mathcal NP }[/math], Метод локальной замены, Метод построения компонент, Метод сужения задачи, Полиномиальная сводимость (трансформируемость), Труднорешаемая задача.
Литература
[Ахо-Хопкрофт-Ульман],
[Гэри-Джонсон],
[Касьянов/95]