Теорема Кука: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Теорема Кука''' (''S.A.Cook, 1971'') - ''задача о выполнимости'' является ''<math>\cal NP</math>-...)
(нет различий)

Версия от 14:58, 2 февраля 2010

Теорема Кука (S.A.Cook, 1971) - задача о выполнимости является [math]\displaystyle{ \cal NP }[/math]-полной.

См. также Задача о вершинном покрытии, Задача о клике, Задача о неэквивалентности регулярных выражений, Задача о разбиении, Задача о точном покрытии 3-множествами, Задача о трехмерном сочетании, Классы [math]\displaystyle{ \cal P }[/math] и [math]\displaystyle{ \cal NP }[/math], Метод локальной замены, Метод построения компонент, Метод сужения задачи, Полиномиальная сводимость (трансформируемость), Труднорешаемая задача.

Литература

[Ахо-Хопкрофт-Ульман],

[Гэри-Джонсон],

[Касьянов/95]