PCP

Пусть , неотрицательные целочисленные функции. Класс сложности состоит из языков, имеющих верифицирующую PCP-систему, которая на входе x :

• потребляет не более случайных бит;
• делает не более запросов к оракулу.

Класс PCP для множеств целочисленных функций R, Q, определяется следующим образом:

Поэтому, например, PCP(log,1) означает класс языков, верифицируемых PCP-системой, потребляющей случайных бит и константу (не обязательно единицу!) ответов от оракула. В том случае, когда определение класса зависит от точного числа запросов к оракулу, применяют обозначения вида PCP(log,q=3),PCP(log,q=3) и т.п.

---

Внимание! Эта статья была создана путем автоматического реплицирования из внутренней базы знаний компании Заказные Информ Системы. Любые правки этой статьи могут быть перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».