Аноним

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

Материал из 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]