Теорема Кука

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

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

Литература

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

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

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