4634
правки
Труднорешаемая задача: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Труднорешаемая задача''' (''Intractable problem'') - задача, для решения которой не су...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Труднорешаемая задача''' (''Intractable problem'') - | '''Труднорешаемая задача''' (''[[Intractable problem]]'') - | ||
задача, для решения которой не | задача, для решения которой не | ||
существует полиномиального алгоритма. | существует [[полиномиальный алгоритм|полиномиального алгоритма]]. | ||
Первые результаты о труднорешаемости задач | Первые результаты о труднорешаемости задач - | ||
полученные А.Тьюрингом около 40 лет назад и ставшие уже | полученные А.Тьюрингом около 40 лет назад и ставшие уже | ||
классическими результаты о неразрешимости ряда задач, для | классическими результаты о неразрешимости ряда задач, для | ||
которых вообще не существует алгоритмов их решения. | которых вообще не существует [[алгоритм|алгоритмов]] их решения. | ||
Например, он доказал ''алгоритмическую неразрешимость'' | Например, он доказал ''алгоритмическую неразрешимость'' | ||
''проблемы остановки'' для ''МТ'' --- невозможно указать алгоритм, | ''проблемы остановки'' для ''МТ'' --- невозможно указать алгоритм, | ||
| Строка 36: | Строка 36: | ||
доказано существование для любого <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> | ||
- размер входа задачи. | |||
Оказалось, что к классу труднорешаемых задач относится | Оказалось, что к классу труднорешаемых задач относится | ||
| Строка 52: | Строка 52: | ||
классов: они либо вовсе неразрешимы, либо труднорешаемы даже | классов: они либо вовсе неразрешимы, либо труднорешаемы даже | ||
на недетерминированном вычислительном устройстве, т.е. | на недетерминированном вычислительном устройстве, т.е. | ||
находятся вне класса <math>\ | находятся вне класса <math>\mathcal NP</math>. | ||
Другое название | Другое название -''[[Трудно разрешаемая задача]].'' | ||
См. также ''Задача о вершинном покрытии, Задача о выполнимости, Задача о клике, Задача о неэквивалентности регулярных выражений, Задача о разбиении, Задача о точном покрытии 3-множествами, | ==См. также == | ||
Задача о трехмерном сочетании, Классы <math>\ | ''[[Задача о вершинном покрытии]], [[Задача о выполнимости]], [[Задача о клике]], [[Задача о неэквивалентности регулярных выражений]], [[Задача о разбиении]], [[Задача о точном покрытии 3-множествами]], | ||
[[Задача о трехмерном сочетании]], [[Классы P и NP|Классы <math>\mathcal P</math> и <math>\mathcal NP</math>]], [[Метод локальной замены]], [[Метод построения компонент]], [[Метод сужения задачи]], [[Полиномиальная сводимость (трансформируемость)]], [[NP-Полная задача|<math>\mathcal NP</math>-полная задача]], [[Труднорешаемая задача]].'' | |||
==Литература== | ==Литература== | ||
[Ахо-Хопкрофт-Ульман], | [Ахо-Хопкрофт-Ульман], | ||