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

'''Труднорешаемая задача''' (''Intractable problem'') -

существует полиномиального алгоритма.

Первые результаты о труднорешаемости задач ---

которых вообще не существует алгоритмов их решения.

''проблемы остановки'' для ''МТ'' --- невозможно указать алгоритм,

доказано существование для любого <math>k</math> таких труднорешаемых

<math>2^{\vdots^{2^n}}</math>, где <math>k</math> --- высота башни степеней, а <math>n</math>

--- размер входа задачи.

находятся вне класса <math>\cal NP</math>.

Другое название ---''Трудно разрешаемая задача.''

См. также ''Задача о вершинном покрытии, Задача о выполнимости, Задача о клике, Задача о неэквивалентности регулярных выражений, Задача о разбиении, Задача о точном покрытии 3-множествами,

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

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

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