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

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


Первые результаты о труднорешаемости задач -
Первые результаты о труднорешаемости задач
полученные А.Тьюрингом около 40 лет назад и ставшие уже
полученные А.Тьюрингом около 40 лет назад и ставшие уже
классическими результаты о неразрешимости ряда задач, для
классическими результаты о неразрешимости ряда задач, для
которых вообще не существует [[алгоритм|алгоритмов]] их решения.
которых вообще не существует [[алгоритм|алгоритмов]] их решения.
Например, он доказал ''алгоритмическую неразрешимость''
Например, он доказал ''алгоритмическую неразрешимость''
''проблемы остановки'' для ''МТ'' --- невозможно указать алгоритм,
''проблемы остановки'' для ''МТ'' невозможно указать алгоритм,
который по произвольной ''МТ'' определял бы, остановится
который по произвольной ''МТ'' определял бы, остановится
эта ''МТ'' на произвольно заданном входе или нет.
эта ''МТ'' на произвольно заданном входе или нет.
Строка 34: Строка 34:
ряду исследователей удалось показать, что некоторые
ряду исследователей удалось показать, что некоторые
"естественные" разрешимые задачи труднорешаемы. Было
"естественные" разрешимые задачи труднорешаемы. Было
доказано существование для любого <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>
- размер входа задачи.
размер входа задачи.


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


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


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


[Гэри-Джонсон],
* Касьянов В.Н.  Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.
 
[Касьянов/95]

Текущая версия от 19:01, 21 сентября 2011

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

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

См. также

Литература

  • Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.
  • Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982.
  • Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.