|
Персональные инструменты |
![]() |
||
|
![]() |
![]() NPМатериал из CustisWikiВерсия от 07:40, 7 декабря 2005; BenderBot (обсуждение | вклад) (реплицировано из внутренней CustisWiki) Это снимок страницы. Он включает старые, но не удалённые версии шаблонов и изображений. Класс задач, разрешимых на недетерминированной машине Тьюринга за полиномиальное время, т.е, через определение класса NTIME:
Можно показать также эквивалентное определение через детерминированную машину Тьюринга. Определение через детерминированную машину ТьюрингаЯзык принадлежит классу NP, если существует детерминированная машина Тьюринга M и некоторый полином p(*) такие, что
Слово y называется обычно «подсказкой», «свидетелем» (witness), «доказательством» (proof).
Диаграмма «ближайших» классов сложности
Внимание! Эта статья была создана путем автоматического реплицирования из внутренней базы знаний компании Заказные Информ Системы. Любые правки этой статьи могут быть перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion». |
![]() |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
![]() |