Персональные инструменты
 

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».