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

Труднорешаемая задача (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]-полная задача.

Литература

• Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.

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

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