NP

Материал из DISCOPAL
Версия от 09:55, 4 августа 2008; WikiSysop (обсуждение) (1 версия)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

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

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

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

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


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

[svg]

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.