4194
правки
Труднорешаемая задача: различия между версиями
Материал из WEGA
Труднорешаемая задача (посмотреть исходный код)
Версия от 19:01, 21 сентября 2011
, 21 сентября 2011нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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>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. | |||
