Введение

Класс сложности, используемый для классификации задач принятия решений.

В теории вычислительной сложности NP (недетерминированное полиномиальное время) — это класс сложности, используемый для классификации задач принятия решений. NP — это множество задач, для которых экземпляры, имеющие ответ "да", обладают полиномиально верифицируемыми доказательствами с помощью детерминированной машины Тьюринга, или, альтернативно, множество задач, разрешимых в полиномиальное время недетерминированной машиной Тьюринга. NP — это множество задач, разрешимых в полиномиальное время недетерминированной машиной Тьюринга. NP — это множество задач, для которых решения могут быть проверены в полиномиальное время детерминированной машиной Тьюринга. Первое определение является основой для аббревиатуры NP: "недетерминированное, полиномиальное время". Эти два определения эквивалентны, поскольку алгоритм, основанный на машине Тьюринга, состоит из двух фаз: первая — это выдвижение гипотезы о решении, генерируемой недетерминированным образом, а вторая — детерминированный алгоритм, проверяющий, является ли эта гипотеза решением задачи. Очевидно, что класс сложности P (все задачи, разрешимые детерминированно в полиномиальное время) содержится в NP (задачи, решения которых могут быть проверены в полиномиальное время), поскольку если задача разрешима в полиномиальное время, то и её решение можно проверить в полиномиальное время, просто решив задачу. Однако NP содержит гораздо больше задач, самые сложные из которых называются NP-полными задачами. Алгоритм, решающий такую задачу в полиномиальное время, способен решить любую другую задачу из NP также в полиномиальное время. Наиболее важная проблема "P против NP" (P = NP?) ставит вопрос о существовании полиномиальных алгоритмов для решения NP-полных задач и, как следствие, всех задач NP. Широко распространено мнение, что это не так. Класс сложности NP связан с классом сложности co-NP, для которого ответ "нет" может быть проверен в полиномиальное время. Вопрос о равенстве этих классов остаётся открытым в теории сложности.

Предыстория

Многие задачи в области компьютерных наук находятся в классе NP, как и децизионные версии многих задач поиска и оптимизации.

Другие характеристики

С точки зрения описательной теории сложности, NP точно соответствует множеству языков, определяемых экзистенциальной логикой второго порядка (теорема Фагина). NP можно рассматривать как очень простой тип интерактивной системы доказательств, где доказывающий предоставляет сертификат доказательства, а верификатор — это детерминированная машина времени, работающая за полиномиальное время, которая его проверяет. Система является полной, поскольку правильная строка доказательства приведёт к принятию, если она существует, и надёжной, поскольку верификатор не может принять, если допустимой строки доказательства нет. Важный результат теории сложности заключается в том, что NP может быть охарактеризована как класс задач, разрешимых с помощью вероятностно проверяемых доказательств, где верификатор использует O(log n) случайных битов и проверяет лишь постоянное число битов строки доказательства (класс PCP(log n, 1)). Неформально это означает, что верификатор NP, описанный выше, можно заменить на тот, который лишь выборочно проверяет несколько позиций в строке доказательства, и, используя ограниченное число случайных выборов, может с высокой вероятностью определить правильный ответ. Это позволяет доказать ряд результатов о сложности аппроксимации.

П.

Все задачи в классе P, обозначенные как... Для любой задачи из P, имея сертификат её решения, мы можем игнорировать этот сертификат и решить задачу за полиномиальное время.

Изоморфизм подграфа

Проблема изоморфизма подграфов заключается в определении, содержит ли граф G подграф, изоморфный графу H.