Класс NP

---

В теории алгоритмов классом NP (от англ. non-deterministic polynomial) называют множество задач разрешимости, решение которых возможно проверить на машине Тьюринга за время, не превосходящее значения некоторого многочлена от размера входных данных, при наличии некоторых дополнительных сведений (так называемого сертификата решения).

Эквивалентно класс NP включает задачи, которые можно за полиномиальное время решить на недетерминированной машине Тьюринга.

Задачи, имеющие полиномиальные по времени алгоритмы решения, можно решать с помощью компьютера значительно быстрее, чем путём прямого перебора, время которого экспоненциально. Это обуславливает практическое значение проблемы о равенстве классов P и NP.

Класс сложности NP определяется для множества языков, то есть множеств слов над конечным алфавитом ${\displaystyle \Sigma }$. Язык L называется принадлежащим классу NP, если существуют двуместный предикат ${\displaystyle R(x,\,y)}$ из класса P (то есть вычислимый за полиномиальное время) и константа ${\displaystyle c>0}$ такие, что для всякого слова x условие «x принадлежит L» равносильно условию «найдётся y длины меньше ${\displaystyle |x|^{c}}$ такой, что верно ${\displaystyle R(x,\,y)}$» (где |x| — длина слова x). Слово y называется сертификатом принадлежности x языку L. Таким образом, если у нас есть слово, принадлежащее языку, и ещё одно слово-свидетель ограниченной длины (которое бывает трудно найти), то мы быстро сможем удостовериться в том, что x действительно принадлежит L.

---