NP

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

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

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

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

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

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

---

Внимание! Эта статья была создана путем автоматического реплицирования из внутренней базы знаний компании Заказные Информ Системы. Любые правки этой статьи могут быть перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».