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