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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
  
 
== Определения ==
 
== Определения ==
 
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Строка 27: Строка 26:
 
Часто <tex>\mathrm{PCP}_{1, {}^1/{}_2}[r(n), q(n)]</tex> обозначают как <tex>\mathrm{PCP}[r(n), q(n)]</tex>.
 
Часто <tex>\mathrm{PCP}_{1, {}^1/{}_2}[r(n), q(n)]</tex> обозначают как <tex>\mathrm{PCP}[r(n), q(n)]</tex>.
 
}}
 
}}
 
  
 
== Свойства ==
 
== Свойства ==
 
 
{{Теорема
 
{{Теорема
 
|statement = <tex>\mathrm{PCP}[0, 0]</tex> = <tex>\mathrm{PCP}[O(log(n)), 0]</tex> = <tex>\mathrm{PCP}[0, O(log(n))]</tex> = <tex>\mathrm{P}</tex>
 
|statement = <tex>\mathrm{PCP}[0, 0]</tex> = <tex>\mathrm{PCP}[O(log(n)), 0]</tex> = <tex>\mathrm{PCP}[0, O(log(n))]</tex> = <tex>\mathrm{P}</tex>
Строка 49: Строка 46:
 
}}
 
}}
  
 +
== Пример ==
 +
{{Теорема
 +
|statement = '''Graph Nonisomorphism(GNI)''' <tex>\in \mathrm{PCP}[poly(n), O(1)]</tex>
 +
|proof =
  
== Пример ==
+
}}

Версия 15:57, 3 июня 2012

PCP(probabilistically checkable proof) - вид доказательства, проверяемого рандомизированным алгоритмом, использующим ограниченное число случайных бит и читающим ограниченное число бит доказательства. Такой алгоритм должен с достаточно высокими вероятностями принимать корректные доказательства и отвергать ошибочные.

Определения

Определение:
[math]\mathrm{PCP}[/math]-системой(системой вероятностно проверяемых доказательств) с полнотой [math]c(n)[/math] и обоснованностью [math]s(n)[/math] над алфавитом [math]\Sigma[/math] для языка [math]L[/math], где [math]0 \le s(n) \le c(n) \le 1[/math], называется пара [math]V[/math]вероятностная машина Тьюринга имеющая доступ к цепочке [math]\pi \in \Sigma^{*} : |\pi| \le 2^{poly(|input|)}[/math] — доказательству, удовлетворяющая следующим свойствам:
  • Полнота: если [math]x \in L[/math], то [math]P(V^{\pi}(x)=1) \ge c(n)[/math] для некоторой [math]\pi[/math].
  • Обоснованность: если [math]x \notin L[/math], то [math]P(V^{\pi}(x)=1) \le s(n)[/math] для любой [math]\pi[/math].


Определение:
Randomness complexity(вероятностной сложностью) [math]r(n)[/math] верификатора [math]V[/math] называется число случайных битов, которое он использует за всё время работы со входом длины [math]n[/math].


Определение:
Query complexity(запросовой сложностью) [math]q(n)[/math] верификатора [math]V[/math] называется число запросов битов из [math]\pi[/math], которое он отсылает за всё время работы со входом длины [math]n[/math].


Определение:
Верификатор [math]V[/math] называется non-adaptive(неадаптивным), если при отправке запроса не использует ответы на предыдущие. Иными словами, его работа не изменится, если все свои запросы он отправит одновременно.


Определение:
Сложностный класс [math]\mathrm{PCP}_{c(n), s(n)}[r(n), q(n)][/math] является объединением языков всех [math]L[/math], для которых существует [math]\mathrm{PCP}[/math]-система над бинарным алфавитом с полнотой [math]c(n)[/math] и обоснованностью [math]s(n)[/math], в которой верификатор [math]V[/math] неадаптивный, работает за полиномиальное время и имеет вероятностную и запросовую сложности соответственно [math]r(n)[/math] и [math]q(n)[/math].
Часто [math]\mathrm{PCP}_{1, {}^1/{}_2}[r(n), q(n)][/math] обозначают как [math]\mathrm{PCP}[r(n), q(n)][/math].


Свойства

Теорема:
[math]\mathrm{PCP}[0, 0][/math] = [math]\mathrm{PCP}[O(log(n)), 0][/math] = [math]\mathrm{PCP}[0, O(log(n))][/math] = [math]\mathrm{P}[/math]
Доказательство:
[math]\triangleright[/math]
  • [math]\mathrm{PCP}[0, 0][/math] = [math]\mathrm{P}[/math]: вероятностная МТ не использует случайные биты и не обращается к доказательству, то есть является обычной детерминированной МТ, работающей за полиномиальное время.
  • [math]\mathrm{PCP}[O(log(n)), 0][/math] = [math]\mathrm{P}[/math]: доступ к [math]O(log(n))[/math] случайных бит не меняет ситуации, так как все возможные строки логарифмической длины детерминированная МТ может сгенерировать и проверить за полиномиальное время.
  • [math]\mathrm{PCP}[0, O(log(n))][/math] = [math]\mathrm{P}[/math]: так как доступа к случайным битам нет, доказательство можно рассматривать как строку логарифмической длины. Все возможные такие строки детерминированная МТ может сгенерировать и проверить за полиномиальное время.
[math]\triangleleft[/math]
Теорема:
[math]\mathrm{PCP}[poly(n), 0][/math] = [math]\mathrm{coRP}[/math]
Доказательство:
[math]\triangleright[/math]
Определение coRP
[math]\triangleleft[/math]
Теорема:
[math]\mathrm{PCP}[0, poly(n)][/math] = [math]\mathrm{NP}[/math]
Доказательство:
[math]\triangleright[/math]
Определение Σ₁
[math]\triangleleft[/math]

Пример

Теорема:
Graph Nonisomorphism(GNI) [math]\in \mathrm{PCP}[poly(n), O(1)][/math]