|
Персональные инструменты |
![]() |
||
|
![]() |
![]() PCPМатериал из CustisWikiВерсия от 07:40, 7 декабря 2005; BenderBot (обсуждение | вклад) (реплицировано из внутренней CustisWiki) Это снимок страницы. Он включает старые, но не удалённые версии шаблонов и изображений. Пусть , неотрицательные целочисленные функции. Класс сложности состоит из языков, имеющих верифицирующую PCP-систему, которая на входе x :
Класс PCP для множеств целочисленных функций R, Q, определяется следующим образом:
Поэтому, например, PCP(log,1) означает класс языков, верифицируемых PCP-системой, потребляющей случайных бит и константу (не обязательно единицу!) ответов от оракула. В том случае, когда определение класса зависит от точного числа запросов к оракулу, применяют обозначения вида PCP(log,q=3),PCP(log,q=3) и т.п. Внимание! Эта статья была создана путем автоматического реплицирования из внутренней базы знаний компании Заказные Информ Системы. Любые правки этой статьи могут быть перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion». |
![]() |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
![]() |