PCP — различия между версиями

Текущая версия на 09:55, 4 августа 2008

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

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

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

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