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).

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

Graph image creation requires permission to upload.


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