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

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


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

Навигация