PCP

Пусть $r,q: N \Rightarrow N$ — неотрицательные целочисленные функции. Класс сложности ${\cal PCP}(r(\cdot), q(\cdot))$ состоит из языков, имеющих верифицирующую PCP-систему, которая на входе x :

• потребляет не более $r(|x|)$ случайных бит;
• делает не более $q(|x|)$ запросов к оракулу.

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

${\cal PCP}(R,Q) \equiv \bigcup_{r \in R, q \in Q} {\cal PCP}(r(\cdot),q(\cdot))$

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

По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.