999
правок
Задача легко решаемая: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KVN (обсуждение | вклад) м (KVN переименовал страницу Задача легко разрешаемая в Задача легко решаемая) |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
Большинство из алгоритмов, имеющих экспоненциальную временную сложность, --- это просто варианты полного перебора, в то время как полиномиальные алгоритмы для решения той или иной задачи удается построить лишь тогда, когда глубоко понята суть решаемой задачи. Поэтому задача не считается '''легко решаемой''' (''[[tractable problem]]'') до тех пор, пока для нее не построен полиномиальный алгоритм, и обычно задачу называют ''[[Труднорешаемая задача|труднорешаемой]] ([[intractable problem]])'', если для ее решения не существует такого алгоритма. | |||
когда глубоко понята суть решаемой задачи. Поэтому задача не считается | |||
Таким образом, класс <math>{\mathcal P}</math> содержит только легко | Таким образом, класс <math>{\mathcal P}</math> содержит только легко решаемые проблемы, а проблемы, выходящие за класс <math>{\mathcal NP}</math>, являются труднорешаемыми. | ||
Хотя [[классы P и NP|классы <math>{\mathcal P}</math> и <math>{\mathcal NP}</math>]] были определены в терминах [[машина Тьюринга|машин Тьюринга]], можно было бы использовать любую из многих других моделей вычислений, в том числе и так называемую ''машину с произвольным доступом к памяти (равнодоступную адресную машину'' или ''РАМ''), которая является достаточно хорошим приближением к классу обычных, | Хотя [[классы P и NP|классы <math>{\mathcal P}</math> и <math>{\mathcal NP}</math>]] были определены в терминах [[машина Тьюринга|машин Тьюринга]], можно было бы использовать любую из многих других моделей вычислений, в том числе и так называемую ''машину с произвольным доступом к памяти (равнодоступную адресную машину'' или ''РАМ''), которая является достаточно хорошим приближением к классу обычных, | ||
| Строка 13: | Строка 12: | ||
реальных ЭВМ, то класс труднорешаемых задач не будет зависеть от выбора конкретной модели, и такой выбор можно осуществлять, исходя из интересов дела и не уменьшая при этом сферы применимости полученных результатов. | реальных ЭВМ, то класс труднорешаемых задач не будет зависеть от выбора конкретной модели, и такой выбор можно осуществлять, исходя из интересов дела и не уменьшая при этом сферы применимости полученных результатов. | ||
==Литература== | ==Литература== | ||
* Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2. | |||
* Касьянов В.Н., Касьянова Е.В. Теория вычислений. — Новосибирск: НГУ, 2018. | |||