* * *
Р в сравнении с NP
Некоторые вычислительные задачи не могут быть решены с помощью детерминированного подхода — другими словами, с помощью процессов, выдающих уникальный и предполагаемый результат. Именно такими являются полиномиальные алгоритмы, работающие за полиномиальное время и выполняющие, например, операции сложения, умножения или решения систем уравнений. В большинстве случаев при использовании подходящих алгоритмов решение может быть найдено за разумное время. Задачи, которые могут быть решены таким образом, называются задачами класса сложности Р. С другой стороны, задачи класса сложности NP, для которых используются недетерминированные алгоритмы, решаются несколькими разными способами без гарантии получения одинакового результата.
Время, необходимое для решения такого рода проблем, намного больше чем для задач класса Р. Ясно, что любая проблема, которая допускает детерминированное решение за полиномиальное время, может быть также решена способом быстрой проверки. Другими словами, любая задача класса Р является также задачей класса NP. Однако на этом этапе нам следует уточнить понятие алгоритма.
Алгоритм можно сравнить с кулинарным рецептом. Он состоит из последовательности кристально ясных инструкций. Например, чтобы решить уравнение вида х — 2 = 8, можно использовать следующий алгоритм.
1. Отделить х (перенеся все члены, не содержащие х, в правую часть).
2. Выполнить сложение в правой части: 8 + 2 = 10.
3. Записать решение: х = 10.
Это задача класса Р, которую можно решить за полиномиальное время: она
очень проста и быстро решается.
Конечно, мы могли бы просто подставить значение, например х = 3, х = —2 и так далее, и времени на вычисления потребовалось бы меньше, так как единственное, что программа должна делать, — это подставлять значение вместо х и проверять равенство. Такой метод не является детерминированным, потому что всегда есть вероятность того, что решение будет неверным. (Мы предполагаем, что у нас есть определенные критерии для выбора диапазона возможных решений, например, условие, что все они должны находиться между 9 и 11.)
Можно поставить и обратный вопрос. Если у нас есть недетерминированный алгоритм, например, подстановки и проверки, можно ли гарантировать, что существует полиномиальный алгоритм, который позволяет решить задачу детерминировано? Другими словами, можем ли мы быть уверены в существовании алгоритма, решающего задачу за полиномиальное время?
