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

'''Теорема Кука''' (''S.A.Cook, 1971'') -

''задача о выполнимости'' является ''<math>\cal NP</math>-полной''.

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