4624
правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Задача легко разрешаемая''' (''Tractable problem'') - Большинство из алгоритмов, имею...) |
KEV (обсуждение | вклад) Нет описания правки |
||
Строка 1: | Строка 1: | ||
'''Задача легко разрешаемая''' (''Tractable problem'') - | '''Задача легко разрешаемая''' (''[[Tractable problem]]'') - Большинство из алгоритмов, имеющих экспоненциальную временную сложность, --- это просто варианты полного перебора, в то время как полиномиальные алгоритмы для решения той или иной задачи удается построить лишь тогда, | ||
Большинство из алгоритмов, имеющих экспоненциальную | когда глубоко понята суть решаемой задачи. Поэтому задача не считается "хорошо решаемой" до тех пор, пока для нее не построен полиномиальный алгоритм, и обычно задачу называют ''труднорешаемой'', если для ее решения не существует такого алгоритма. | ||
временную сложность, --- это просто варианты полного | |||
перебора, в то время как полиномиальные алгоритмы для | |||
решения той или иной задачи удается построить лишь тогда, | |||
когда глубоко понята суть решаемой задачи. Поэтому задача не | |||
считается "хорошо решаемой" до тех пор, пока для нее не | |||
построен полиномиальный алгоритм, и обычно задачу называют | |||
''труднорешаемой'', если для ее решения не существует | |||
такого алгоритма. | |||
Таким образом, класс | Таким образом, класс <math>{\mathcal P}</math> содержит только легко разрешимые задачи, а задачи, выходящие за класс <math>{\mathcal NP}</math>, являются труднорешаемыми. | ||
<math>{\ | |||
а задачи, выходящие за класс <math>{\ | |||
труднорешаемыми. | |||
Хотя классы <math>{\ | Хотя классы <math>{\mathcal P}</math> и <math>{\mathcal NP}</math> были определены в терминах [[машина Тьюринга|машин Тьюринга]], можно было бы использовать любую из многих других моделей вычислений, в том числе и так называемую ''машину с произвольным доступом к памяти (равнодоступную адресную машину'' или ''РАМ''), которая является достаточно хорошим приближением к классу обычных, | ||
терминах машин Тьюринга, можно было бы использовать любую из | традиционных вычислительных машин с точки зрения представления данных и алгоритмов, целиком помещающихся в оперативной памяти и имеющих дело с элементарными значениями, длины двоичных представлений которых ограничены некоторой константой. | ||
многих других моделей вычислений, в том числе и так | |||
называемую ''машину с произвольным доступом к памяти | |||
(равнодоступную адресную машину'' или ''РАМ''), которая | |||
является достаточно хорошим приближением к классу обычных, | |||
традиционных вычислительных машин с точки зрения | |||
представления данных и алгоритмов, целиком помещающихся в | |||
оперативной памяти и имеющих дело с элементарными | |||
значениями, длины двоичных представлений которых ограничены | |||
некоторой константой. | |||
Все известные в настоящее время реалистические модели ЭВМ (в | Все известные в настоящее время реалистические модели ЭВМ (в их детерминированном и недетерминированном вариантах) эквивалентны относительно полиномиальной временной | ||
их детерминированном и недетерминированном вариантах) | сложности. Можно ожидать, что и любая иная "разумная" модель ЭВМ будет эквивалентна в указанном смысле всем перечисленным моделям. | ||
эквивалентны относительно полиномиальной временной | |||
сложности. Можно ожидать, что и любая иная "разумная" модель | |||
ЭВМ будет эквивалентна в указанном смысле всем перечисленным | |||
моделям. | |||
Под словами "разумная модель" здесь главным образом имеется | Под словами "разумная модель" здесь главным образом имеется в виду то, что объем работы, выполняемой машиной в единицу времени, ограничен (сверху) полиномом. Так, например, модель, обладающая способностью выполнять параллельно произвольно много операций, не будет считаться "разумной", и в действительности ни одна из существующих (или проектируемых) ЭВМ не обладает подобным свойством. Во всяком случае, если ограничиться рассмотрением стандартных моделей | ||
в виду то, что объем работы, выполняемой машиной в единицу | реальных ЭВМ, то класс труднорешаемых задач не будет зависеть от выбора конкретной модели, и такой выбор можно осуществлять, исходя из интересов дела и не уменьшая при этом сферы применимости полученных результатов. | ||
времени, ограничен (сверху) полиномом. Так, например, | |||
модель, обладающая способностью выполнять параллельно | |||
произвольно много операций, не будет считаться "разумной", и | |||
в действительности ни одна из существующих (или | |||
проектируемых) ЭВМ не обладает подобным свойством. Во всяком | |||
случае, если ограничиться рассмотрением стандартных моделей | |||
реальных ЭВМ, то класс труднорешаемых задач не будет | |||
зависеть от выбора конкретной модели, и такой выбор можно | |||
осуществлять, исходя из интересов дела и не уменьшая при | |||
этом сферы применимости полученных результатов. | |||
==Литература== | ==Литература== | ||
[Ахо-Хопкрофт-Ульман], | [Ахо-Хопкрофт-Ульман], | ||
[Касьянов/95] | [Касьянов/95] |