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