Персональные инструменты
 

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

Материал из CustisWiki

Перейти к: навигация, поиск
м (реплицировано из внутренней CustisWiki)
 
м (Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»)
 
(не показана 1 промежуточная версия 1 участника)
Строка 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}}
+

Текущая версия на 20:39, 13 июня 2011

  1. REDIRECT discopal:PCP