NP

From Традиция
Jump to navigation Jump to search

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

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

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

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

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

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

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

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

Error: No valid link was found at the end of line 2.


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