Аноним

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

Материал из WEGA
нет описания правки
(Создана новая страница размером '''Труднорешаемая задача''' (''Intractable problem'') - задача, для решения которой не су...)
 
Нет описания правки
Строка 1: Строка 1:
'''Труднорешаемая задача''' (''Intractable problem'') -  
'''Труднорешаемая задача''' (''[[Intractable problem]]'') -  
задача, для решения которой не
задача, для решения которой не
существует полиномиального алгоритма.
существует [[полиномиальный алгоритм|полиномиального алгоритма]].


Первые результаты о труднорешаемости задач ---
Первые результаты о труднорешаемости задач -
полученные А.Тьюрингом около 40 лет назад и ставшие уже
полученные А.Тьюрингом около 40 лет назад и ставшие уже
классическими результаты о неразрешимости ряда задач, для
классическими результаты о неразрешимости ряда задач, для
которых вообще не существует алгоритмов их решения.
которых вообще не существует [[алгоритм|алгоритмов]] их решения.
Например, он доказал ''алгоритмическую неразрешимость''
Например, он доказал ''алгоритмическую неразрешимость''
''проблемы остановки'' для ''МТ'' --- невозможно указать алгоритм,
''проблемы остановки'' для ''МТ'' --- невозможно указать алгоритм,
Строка 36: Строка 36:
доказано существование для любого <math>k</math> таких труднорешаемых
доказано существование для любого <math>k</math> таких труднорешаемых
задач, временная сложность решения которых больше чем
задач, временная сложность решения которых больше чем
<math>2^{\vdots^{2^n}}</math>, где <math>k</math> --- высота башни степеней, а <math>n</math>
<math>2^{\vdots^{2^n}}</math>, где <math>k</math> - высота башни степеней, а <math>n</math>
--- размер входа задачи.
- размер входа задачи.


Оказалось, что к классу труднорешаемых задач относится
Оказалось, что к классу труднорешаемых задач относится
Строка 52: Строка 52:
классов: они либо вовсе неразрешимы, либо труднорешаемы даже
классов: они либо вовсе неразрешимы, либо труднорешаемы даже
на недетерминированном вычислительном устройстве, т.е.
на недетерминированном вычислительном устройстве, т.е.
находятся вне класса <math>\cal NP</math>.
находятся вне класса <math>\mathcal NP</math>.


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


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