Труднорешаемая задача

Труднорешаемая задача (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{ \cal NP }[/math].

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

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

Литература

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

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

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