WikiSysop: 1 версия

2008-08-04T09:55:49Z

1 версия

Новая страница

Пусть <amsmath>r,q: N \Rightarrow N</amsmath>, неотрицательные целочисленные функции. Класс сложности <amsmath>{\cal PCP}(r(\cdot),q(\cdot))</amsmath> состоит из языков, имеющих верифицирующую [[PCP-система|PCP-систему]], которая на входе ''x'' :
* потребляет не более <amsmath>r(|x|)</amsmath> случайных бит;
* делает не более <amsmath>q(|x|)</amsmath> запросов к оракулу.

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

<amsmath>
{\cal PCP}(R,Q) \equiv \bigcup_{r \in R, q \in Q} {\cal PCP}(r(\cdot),q(\cdot))
</amsmath>

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

[[Category:Классы сложности]]
{{replicate-from-custiswiki-to-lib}}

PCP - История изменений

WikiSysop: 1 версия