ВУЗ:
Составители:
Сложностный класс NP – это класс языков, для которых существуют проверяющие
алгоритмы, работающие полиномиальное время, причем длина сертификата также
ограничена некоторым полиномом.
Более точно, язык L принадлежит классу NP, если существует такой полиномиальный
алгоритм A с двумя аргументами и такой многочлен p(x) с целыми коэффициентами, что
L = {x ∈ {0, 1}
*
: существует сертификат y, для которого |y| ≤ p(|x|) и A(x, y) = 1}.
В этом случае мы говорим, что алгоритм A проверяет язык L за полиномиальное время.
Несколько слов о названии: сокращение NP происходит от английских слов
Nondeterministic Polynomial (time), что переводится как недетерминированное
полиномиальное время. Первоначально класс NP определялся в терминах так называемых
недетерминированных вычислений.
Мы уже знаем одну задачу из класса NP – это задача HAM-CYCLE. Кроме того,
всякая задача из P принадлежит также и NP. Действительно, если есть полиномиальный
алгоритм, распознающий язык, то легко построить проверяющий алгоритм для того же
языка – проверяющий алгоритм может просто игнорировать свой второй аргумент
(сертификат). Таким образом, P ⊆ NP.
В данное время неизвестно, совпадают ли классы P и NP, но большинство
специалистов полагают, что нет.
Интуитивно класс P можно представлять себе как
класс задач, которые можно быстро
решить, а класс NP – как класс задач, решение которых может быть быстро проверено.
На практике решить самому задачу часто намного труднее, чем проверить уже готовое
решение, особенно если время работы ограничено. По аналогии можно думать, что в
классе NP имеются задачи, которые нельзя решить за полиномиальное время.
6.4 NP-полнота и сводимость
По-видимому, наиболее убедительным аргументом в пользу того, что классы P и
NP различны, является существование так называемых NP-полных задач. Этот класс
обладает удивительным свойством: если какая-нибудь NP-полная задача разрешима за
полиномиальное время, то и все задачи из класса NP разрешимы за полиномиальное
время, т.е. P = NP
. Несмотря на многолетние исследования, ни для одной NP-полной
задачи не найден полиномиальный разрешающий алгоритм.
В частности, задача HAM-CYCLE (о гамильтоновом цикле) является NP-полной.
Таким образом, научившись решать её за полиномиальное время, мы получим
полиномиальные алгоритмы для всех задач класса NP. Переформулировка: если
множество NP\P не пусто, то HAM-CYCLE ∈ NP
\P.
Неформально говоря, NP-полные языки являются самыми «трудными» в классе
NP. При этом трудность языков можно сравнивать, сводя один язык к другому. В этом
разделе мы даём определение сводимости, затем определяем класс NP-полных задач и
устанавливаем полноту многих задач.
Говоря неформально, задача Q сводится к задаче R, если
задачу Q можно решить
для любого входа, считая известным решение задачи R для какого-то другого входа.
Например, задача решения линейного уравнения сводится к задаче решения квадратного
уравнения (линейное уравнение можно превратить в квадратное, добавив фиктивный
старший член). Если задача Q сводится к задаче R, то любой алгоритм, решающий R,
можно
использовать для решения задачи Q, т.е. Q «не труднее» R.
