|
|
| Строка 1: |
Строка 1: |
| − | Пусть <amsmath>r,q: N \Rightarrow N</amsmath>, неотрицательные целочисленные функции. Класс сложности <amsmath>{\cal PCP}(r(\cdot),q(\cdot))</amsmath> состоит из языков, имеющих верифицирующую [[PCP-система|PCP-систему]], которая на входе ''x'' :
| + | #REDIRECT [[discopal:{{PAGENAME}}]] |
| − | * потребляет не более <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}}
| + | |
