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

Материал из 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>-полная задача]], [[Труднорешаемая задача]].''
==Литература==
==Литература==
[Ахо-Хопкрофт-Ульман],  
[Ахо-Хопкрофт-Ульман],  

Версия от 17:23, 7 февраля 2010

Труднорешаемая задача (Intractable problem) - задача, для решения которой не существует полиномиального алгоритма.

Первые результаты о труднорешаемости задач - полученные А.Тьюрингом около 40 лет назад и ставшие уже классическими результаты о неразрешимости ряда задач, для которых вообще не существует алгоритмов их решения. Например, он доказал алгоритмическую неразрешимость проблемы остановки для МТ --- невозможно указать алгоритм, который по произвольной МТ определял бы, остановится эта МТ на произвольно заданном входе или нет. В настоящее время известно большое число других (алгоритмически) неразрешимых задач из разных разделов дискретной математики. К ним относится, например, задача выяснения тривиальности конечно-порожденных групп, десятая задача Гильберта (разрешимости в целых числах полиномиальных уравнений), ряд задач о покрытии области равными областями и многие другие.

На практике, однако, мы не можем довольствоваться констатацией того, что данная задача является разрешимой. Нам, как правило, нужны алгоритмы, предъявляющие при своем выполнении разумные требования к ресурсам используемых вычислительных устройств. Вместе с тем далеко не все разрешимые задачи являются реально разрешимыми, и существует феномен труднорешаемых разрешимых задач.

Первые примеры труднорешаемых разрешимых задач были получены в начале 60-х годов в работах Дж.Хартманниса и Р.Стирнза по "иерархии" сложности. Однако их примеры включали только "искусственные" (специально построенные) задачи. Только в начале 70-х А.Мейеру, Л.Стокмейеру, М.Фишеру, М.Рабину и ряду исследователей удалось показать, что некоторые "естественные" разрешимые задачи труднорешаемы. Было доказано существование для любого [math]\displaystyle{ k }[/math] таких труднорешаемых задач, временная сложность решения которых больше чем [math]\displaystyle{ 2^{\vdots^{2^n}} }[/math], где [math]\displaystyle{ k }[/math] - высота башни степеней, а [math]\displaystyle{ n }[/math] - размер входа задачи.

Оказалось, что к классу труднорешаемых задач относится большое число изучавшихся ранее задач из теории автоматов, теории формальных языков, математической логики и других разделов дискретной математики. Причем эти задачи не могут быть эффективно (за полиномиальное время) решены даже с помощью недетерминированного вычислительного устройства, обладающего способностью параллельно выполнять неограниченное количество независимых вычислений.

Все известные задачи, труднорешаемость которых доказана, попадают в один из рассмотренных выше классов: они либо вовсе неразрешимы, либо труднорешаемы даже на недетерминированном вычислительном устройстве, т.е. находятся вне класса [math]\displaystyle{ \mathcal NP }[/math].

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

См. также

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

Литература

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

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

[Касьянов/95]