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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Теорема Кука''' (''S.A.Cook, 1971'') - ''задача о выполнимости'' является ''<math>\cal NP</math>-...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 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>]],''
* ''[[Метод локальной замены]],''
* ''[[Метод построения компонент]],''
* ''[[Метод сужения задачи]],''
* ''[[Полиномиальная сводимость (трансформируемость)]],''
* ''[[Труднорешаемая задача]].''
==Литература==
==Литература==
[Ахо-Хопкрофт-Ульман],
* Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. —  М.: Мир, 1979.


[Гэри-Джонсон],
* Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982.


[Касьянов/95]
* Касьянов В.Н.  Лекции по теории формальных языков, автоматов и сложности вычислений. —
Новосибирск: НГУ, 1995.

Текущая версия от 11:41, 15 сентября 2011

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

См. также

Литература

  • Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.
  • Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982.
  • Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. —

Новосибирск: НГУ, 1995.