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.Список авторов доступен на этом ресурсе в статье под тем же названием.