Задача легко решаемая

Большинство из алгоритмов, имеющих экспоненциальную временную сложность, --- это просто варианты полного перебора, в то время как полиномиальные алгоритмы для решения той или иной задачи удается построить лишь тогда, когда глубоко понята суть решаемой задачи. Поэтому задача не считается легко решаемой (tractable problem) до тех пор, пока для нее не построен полиномиальный алгоритм, и обычно задачу называют труднорешаемой (intractable problem), если для ее решения не существует такого алгоритма.

Таким образом, класс [math]\displaystyle{ {\mathcal P} }[/math] содержит только легко решаемые проблемы, а проблемы, выходящие за класс [math]\displaystyle{ {\mathcal NP} }[/math], являются труднорешаемыми.

Хотя классы [math]\displaystyle{ {\mathcal P} }[/math] и [math]\displaystyle{ {\mathcal NP} }[/math] были определены в терминах машин Тьюринга, можно было бы использовать любую из многих других моделей вычислений, в том числе и так называемую машину с произвольным доступом к памяти (равнодоступную адресную машину или РАМ), которая является достаточно хорошим приближением к классу обычных, традиционных вычислительных машин с точки зрения представления данных и алгоритмов, целиком помещающихся в оперативной памяти и имеющих дело с элементарными значениями, длины двоичных представлений которых ограничены некоторой константой.

Все известные в настоящее время реалистические модели ЭВМ (в их детерминированном и недетерминированном вариантах) эквивалентны относительно полиномиальной временной сложности. Можно ожидать, что и любая иная "разумная" модель ЭВМ будет эквивалентна в указанном смысле всем перечисленным моделям.

Под словами "разумная модель" здесь главным образом имеется в виду то, что объем работы, выполняемой машиной в единицу времени, ограничен (сверху) полиномом. Так, например, модель, обладающая способностью выполнять параллельно произвольно много операций, не будет считаться "разумной", и в действительности ни одна из существующих (или проектируемых) ЭВМ не обладает подобным свойством. Во всяком случае, если ограничиться рассмотрением стандартных моделей реальных ЭВМ, то класс труднорешаемых задач не будет зависеть от выбора конкретной модели, и такой выбор можно осуществлять, исходя из интересов дела и не уменьшая при этом сферы применимости полученных результатов.

Литература

• Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.
• Касьянов В.Н., Касьянова Е.В. Теория вычислений. — Новосибирск: НГУ, 2018.