NP

Класс задач, разрешимых на недетерминированной машине Тьюринга за полиномиальное время, т.е, через определение класса NTIME:

${\cal NP} \equiv \cup_{c>0} {\cal NTIME}(n^c)$

Можно показать также эквивалентное определение через детерминированную машину Тьюринга.

Определение через детерминированную машину Тьюринга

Язык $L \subseteq \Sigma^*$ принадлежит классу NP, если существует детерминированная машина Тьюринга M и некоторый полином p(*) такие, что

$L=\{ x \in \Sigma^* : \ \exists \ y, \ |y|$

Слово y называется обычно «подсказкой», «свидетелем» (witness), «доказательством» (proof).

Диаграмма «ближайших» классов сложности

По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.