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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Свойства)
(не показано 36 промежуточных версий 6 участников)
Строка 5: Строка 5:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
<tex>\mathrm{PCP}</tex>'''-системой'''(системой вероятностно проверяемых доказательств) с полнотой <tex>c(n)</tex> и обоснованностью <tex>s(n)</tex> над алфавитом <tex>\Sigma</tex> для языка <tex>L</tex>, где <tex>0 \le s(n) \le c(n) \le 1</tex>, называется пара <tex>V</tex> {{---}} [[Вероятностные вычисления. Вероятностная машина Тьюринга#Основные определения|вероятностная машина Тьюринга]] имеющая доступ к цепочке <tex>\pi \in \Sigma^{*} : |\pi| \le 2^{poly(|input|)}</tex> {{---}} доказательству, удовлетворяющая следующим свойствам:
+
<tex>\mathrm{PCP}</tex>'''-системой''' (системой вероятностно проверяемых доказательств) с полнотой <tex>c(n)</tex> и обоснованностью <tex>s(n)</tex> над алфавитом <tex>\Sigma</tex> для языка <tex>L</tex>, где <tex>0 \le s(n) \le c(n) \le 1</tex>, называется верификатор <tex>V</tex> {{---}} [[Вероятностные вычисления. Вероятностная машина Тьюринга#Основные определения|вероятностная машина Тьюринга]], имеющая доступ к доказательству <tex>\pi</tex> {{---}} цепочке из <tex>\Sigma^{*}</tex>, удовлетворяющая следующим свойствам:
* '''Полнота''': если <tex>x \in L</tex>, то <tex>P(V^{\pi}(x)=1) \ge c(n)</tex> для некоторой <tex>\pi</tex>.
+
* '''Полнота''': если <tex>x \in L</tex>, то вероятность того, что <tex>V^{\pi}</tex> допустит <tex>x</tex>, не меньше <tex>c(n)</tex> для некоторого <tex>\pi</tex>,
* '''Обоснованность''': если <tex>x \notin L</tex>, то <tex>P(V^{\pi}(x)=1) \le s(n)</tex> для любой <tex>\pi</tex>.
+
* '''Обоснованность''': если <tex>x \notin L</tex>, то вероятность того, что <tex>V^{\pi}</tex> допустит <tex>x</tex>, не больше <tex>s(n)</tex> для любого <tex>\pi</tex>.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Randomness complexity'''(вероятностной сложностью) <tex>r(n)</tex> верификатора <tex>V</tex> называется число случайных битов, которое он использует за всё время работы со входом длины <tex>n</tex>.
+
'''Randomness complexity''' (вероятностной сложностью) <tex>r(n)</tex> верификатора <tex>V</tex> называется число случайных битов, используемых за всё время работы со входом длины <tex>n</tex>.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Query complexity'''(запросовой сложностью) <tex>q(n)</tex> верификатора <tex>V</tex> называется число запросов битов из <tex>\pi</tex>, которое он отсылает за всё время работы со входом длины <tex>n</tex>.
+
'''Query complexity''' (запросной сложностью) <tex>q(n)</tex> верификатора <tex>V</tex> называется число запросов битов из <tex>\pi</tex>, отсылаемых за всё время работы со входом длины <tex>n</tex>.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Верификатор <tex>V</tex> называется '''non-adaptive'''(неадаптивным), если при отправке запроса не использует ответы на предыдущие. Иными словами, его работа не изменится, если все свои запросы он отправит одновременно.
+
Верификатор <tex>V</tex> называется '''non-adaptive''' (неадаптивным), если при отправке запроса не использует ответы на предыдущие. Иными словами, его работа не изменится, если все запросы отправить одновременно.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Сложностный класс <tex>\mathrm{PCP}_{c(n), s(n)}[r(n), q(n)]</tex> является объединением языков всех <tex>L</tex>, для которых существует <tex>\mathrm{PCP}</tex>-система над бинарным алфавитом с полнотой <tex>c(n)</tex> и обоснованностью <tex>s(n)</tex>, в которой верификатор <tex>V</tex> неадаптивный, работает за полиномиальное время и имеет вероятностную и запросовую сложности соответственно <tex>r(n)</tex> и <tex>q(n)</tex>.<br/>
+
Сложностный класс <tex>\mathrm{PCP}_{c(n), s(n)}[r(n), q(n)]</tex> {{---}} это объединение всех языков, для которых существует <tex>\mathrm{PCP}</tex>-система над бинарным алфавитом с полнотой <tex>c(n)</tex> и обоснованностью <tex>s(n)</tex>, в которой неадаптивный верификатор <tex>V</tex> работает за полиномиальное время и имеет вероятностную и запросную сложности соответственно <tex>r(n)</tex> и <tex>q(n)</tex>, а доказательства имеют экспоненциальную длину.<br/>
Часто <tex>\mathrm{PCP}_{1, {}^1/{}_2}[r(n), q(n)]</tex> обозначают как <tex>\mathrm{PCP}[r(n), q(n)]</tex>.
+
Часто <tex>\mathrm{PCP}_{1, \frac{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>.
 
|proof =
 
|proof =
* <tex>\mathrm{PCP}[0, 0]</tex> = <tex>\mathrm{P}</tex>: вероятностная МТ не использует случайные биты и не обращается к доказательству, то есть является обычной детерминированной МТ, работающей за полиномиальное время.
+
* <tex>\mathrm{PCP}[0, 0]</tex> = <tex>\mathrm{P}</tex>: вероятностная МТ не использует случайные биты и не обращается к доказательству, то есть работает как детерминированная МТ, работающая за полиномиальное время.
* <tex>\mathrm{PCP}[O(log(n)), 0]</tex> = <tex>\mathrm{P}</tex>: доступ к <tex>O(log(n))</tex> случайных бит не меняет ситуации, так как все возможные строки логарифмической длины детерминированная МТ может сгенерировать и проверить за полиномиальное время.
+
* <tex>\mathrm{PCP}[O(\log(n)), 0]</tex> = <tex>\mathrm{P}</tex>: доступ к <tex>O(\log(n))</tex> случайных бит не меняет ситуации, так как все возможные битовые цепочки логарифмической длины детерминированная МТ может сгенерировать и проверить за полиномиальное время.
* <tex>\mathrm{PCP}[0, O(log(n))]</tex> = <tex>\mathrm{P}</tex>: так как доступа к случайным битам нет, доказательство можно рассматривать как строку логарифмической длины. Все возможные такие строки детерминированная МТ может сгенерировать и проверить за полиномиальное время.
+
* <tex>\mathrm{PCP}[0, O(\log(n))]</tex> = <tex>\mathrm{P}</tex>: так как доступа к случайным битам нет, <tex>\pi</tex> можно рассматривать как битовую цепочку логарифмической длины. Все возможные такие цепочки детерминированная МТ может сгенерировать и проверить за полиномиальное время.
 
}}
 
}}
 
{{Теорема
 
{{Теорема
|statement = <tex>\mathrm{PCP}[poly(n), 0]</tex> = <tex>\mathrm{coRP}</tex>
+
|statement = <tex>\mathrm{PCP}[poly(n), 0]</tex> = <tex>\mathrm{coRP}</tex>.
 
|proof =
 
|proof =
[[Вероятностные вычисления. Вероятностная машина Тьюринга#Вероятностные сложностные классы|Определение coRP]]
+
Очевидно следует из [[Классы RP и coRP#Определения|определения coRP]].
 
}}
 
}}
 
{{Теорема
 
{{Теорема
|statement = <tex>\mathrm{PCP}[0, poly(n)]</tex> = <tex>\mathrm{NP}</tex>
+
|statement = <tex>\mathrm{PCP}[0, poly(n)]</tex> = <tex>\mathrm{NP}</tex>.
 
|proof =
 
|proof =
[[Недетерминированные вычисления. Классы NP и Σ₁#Классы NP и Σ₁|Определение Σ₁]]
+
Очевидно следует из [[Классы_NP_и_Σ₁|определения Σ₁]].
 +
}}
 +
{{Теорема
 +
|id=pcp_th
 +
|about=[[PCP-теорема]]
 +
|statement=<tex>\mathrm{PCP}[log(n), O(1)] = \mathrm{NP}</tex>
 +
|proof=
 +
В одну сторону включение тривиально <tex>\mathrm{PCP}(\log n, 1) \subseteq \mathrm{NTIME}(2^{O(\log n)}) = NP</tex>.
 +
 
 +
Обратное включение <tex>NP \subseteq \mathrm{PCP}(\log n, 1)</tex> нетривиально и рассматривается в [[PCP-теорема | PCP-теореме]].
 
}}
 
}}
  
 
== Пример ==
 
== Пример ==
 
{{Теорема
 
{{Теорема
|statement = '''Graph Nonisomorphism(GNI)''' <tex>\in \mathrm{PCP}[poly(n), O(1)]</tex>
+
|statement = '''Graph Nonisomorphism(GNI)''' <tex>\in \mathrm{PCP}[poly(n), O(1)]</tex>.
 
|proof =
 
|proof =
Даны графы на <tex>n</tex> вершинах <tex>G_1</tex> и <tex>G_2</tex>. Требуется проверить, изоморфны ли они друг другу. <br/>
+
<tex>G_1</tex> и <tex>G_2</tex> {{---}} графы на <tex>n</tex> вершинах. Требуется проверить, неизоморфны ли они друг другу. <br/>
 
Сперва пронумеруем все возможные графы на <tex>n</tex> вершинах. Не умаляя общности, будем считать, что <tex>\pi</tex> над троичным алфавитом. <br/>
 
Сперва пронумеруем все возможные графы на <tex>n</tex> вершинах. Не умаляя общности, будем считать, что <tex>\pi</tex> над троичным алфавитом. <br/>
 
Будем считать корректной <tex>\pi</tex>:<br/>
 
Будем считать корректной <tex>\pi</tex>:<br/>
* <tex>\pi[k] = 0</tex> тогда и только тогда, когда граф номер <tex>k</tex> изоморфен <tex>G_1</tex> и <tex>G_2</tex>;
+
* <tex>\pi[k] = 0</tex> тогда и только тогда, когда граф номер <tex>k</tex> изоморфен <tex>G_1</tex> и <tex>G_2</tex>,
* <tex>\pi[k] = 1</tex> тогда и только тогда, когда граф номер <tex>k</tex> изоморфен <tex>G_1</tex> и неизоморфен <tex>G_2</tex>;
+
* <tex>\pi[k] = 1</tex> тогда и только тогда, когда граф номер <tex>k</tex> изоморфен <tex>G_1</tex> и неизоморфен <tex>G_2</tex>,
 
* <tex>\pi[k] = 2</tex> тогда и только тогда, когда граф номер <tex>k</tex> неизоморфен <tex>G_1</tex> и изоморфен <tex>G_2</tex>.
 
* <tex>\pi[k] = 2</tex> тогда и только тогда, когда граф номер <tex>k</tex> неизоморфен <tex>G_1</tex> и изоморфен <tex>G_2</tex>.
 
Верификатором <tex>V</tex> будет вероятностная МТ, работающая эквивалентно следующему псевдокоду:<br/>
 
Верификатором <tex>V</tex> будет вероятностная МТ, работающая эквивалентно следующему псевдокоду:<br/>
Строка 61: Строка 70:
 
     <tex>\phi</tex> = random permutation{1..n};
 
     <tex>\phi</tex> = random permutation{1..n};
 
     <tex>H</tex> = <tex>\phi(G_i)</tex>;
 
     <tex>H</tex> = <tex>\phi(G_i)</tex>;
     return <tex>\pi[\#H] == i</tex>;
+
     if (<tex>\pi[\#H]</tex> == 0) or (<tex>\pi[\#H]</tex> == 3-i) {
 +
      return 0;
 +
    }
 +
    // <tex>\pi[\#H]</tex> == i
 +
    return 1;
 
   }
 
   }
 
Проверим полноту и обоснованность:
 
Проверим полноту и обоснованность:
* '''Полнота''': если графы неизоморфны, то существует <tex>\pi</tex> такая, что всякий её символ равен 1 или 2 и задан корректно. Тогда на этой <tex>\pi</tex> верификатор всегда вернёт 1.
+
* '''Полнота''': если графы неизоморфны, то существует <tex>\pi</tex> такая, что всякий её символ равен 1 или 2 и задан корректно. Тогда на этой <tex>\pi</tex> верификатор всегда вернёт 1;
* '''Обоснованность''': если графы изоморфны, то благодаря случайному выбору <tex>i</tex> вероятность ошибки не превышает <tex>{}^1/{}_2</tex>.
+
* '''Обоснованность''': если графы изоморфны, то фиксируем <tex>\pi</tex>. Пусть <tex>\Omega</tex> {{---}} это множество всех конфигураций случайной ленты, с которой работает <tex>V</tex>. Заметим, что все конфигурации из <tex>\Omega</tex> будут переданы <tex>V</tex> с равными вероятностями. Теперь рассмотрим произвольную конфигурацию типа <tex>\psi</tex> из <tex>\Omega</tex>, то есть конфигурацию, на которой <tex>V</tex> допускает <tex>\langle G_1, G_2 \rangle</tex>. Заметим, что для каждой такой конфигурации существует однозначно определяемая конфигурация типа <tex>\overline \psi</tex>, отличающаяся от <tex>\psi</tex> только первым битом и также принадлежащая <tex>\Omega</tex>. Запустившись на <tex>\overline \psi</tex>, <tex>V</tex>, очевидно, отвергнет <tex>\langle G_1, G_2 \rangle</tex>. Таким образом, конфигураций типа <tex>\psi</tex> в <tex>\Omega</tex> не больше половины. Как уже отмечалось, конфигурации из <tex>\Omega</tex> подаются <tex>V</tex> с равными вероятностями, а конфигураций не из <tex>\Omega</tex>, по определению, <tex>V</tex> не подаётся. Таким образом, вероятность ошибки не превышает <tex>\frac{1}{2}</tex>.
 
}}
 
}}

Версия 13:38, 12 февраля 2017

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[/math] — цепочке из [math]\Sigma^{*}[/math], удовлетворяющая следующим свойствам:
  • Полнота: если [math]x \in L[/math], то вероятность того, что [math]V^{\pi}[/math] допустит [math]x[/math], не меньше [math]c(n)[/math] для некоторого [math]\pi[/math],
  • Обоснованность: если [math]x \notin L[/math], то вероятность того, что [math]V^{\pi}[/math] допустит [math]x[/math], не больше [math]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]\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, \frac{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]\pi[/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]
Теорема (PCP-теорема):
[math]\mathrm{PCP}[log(n), O(1)] = \mathrm{NP}[/math]
Доказательство:
[math]\triangleright[/math]

В одну сторону включение тривиально [math]\mathrm{PCP}(\log n, 1) \subseteq \mathrm{NTIME}(2^{O(\log n)}) = NP[/math].

Обратное включение [math]NP \subseteq \mathrm{PCP}(\log n, 1)[/math] нетривиально и рассматривается в PCP-теореме.
[math]\triangleleft[/math]

Пример

Теорема:
Graph Nonisomorphism(GNI) [math]\in \mathrm{PCP}[poly(n), O(1)][/math].
Доказательство:
[math]\triangleright[/math]

[math]G_1[/math] и [math]G_2[/math] — графы на [math]n[/math] вершинах. Требуется проверить, неизоморфны ли они друг другу.
Сперва пронумеруем все возможные графы на [math]n[/math] вершинах. Не умаляя общности, будем считать, что [math]\pi[/math] над троичным алфавитом.
Будем считать корректной [math]\pi[/math]:

  • [math]\pi[k] = 0[/math] тогда и только тогда, когда граф номер [math]k[/math] изоморфен [math]G_1[/math] и [math]G_2[/math],
  • [math]\pi[k] = 1[/math] тогда и только тогда, когда граф номер [math]k[/math] изоморфен [math]G_1[/math] и неизоморфен [math]G_2[/math],
  • [math]\pi[k] = 2[/math] тогда и только тогда, когда граф номер [math]k[/math] неизоморфен [math]G_1[/math] и изоморфен [math]G_2[/math].

Верификатором [math]V[/math] будет вероятностная МТ, работающая эквивалентно следующему псевдокоду:

 p([math]\langle G_1, G_2 \rangle[/math]) {
   i = random{1, 2};
   [math]\phi[/math] = random permutation{1..n};
   [math]H[/math] = [math]\phi(G_i)[/math];
   if ([math]\pi[\#H][/math] == 0) or ([math]\pi[\#H][/math] == 3-i) {
     return 0;
   }
   // [math]\pi[\#H][/math] == i
   return 1;
 }

Проверим полноту и обоснованность:

  • Полнота: если графы неизоморфны, то существует [math]\pi[/math] такая, что всякий её символ равен 1 или 2 и задан корректно. Тогда на этой [math]\pi[/math] верификатор всегда вернёт 1;
  • Обоснованность: если графы изоморфны, то фиксируем [math]\pi[/math]. Пусть [math]\Omega[/math] — это множество всех конфигураций случайной ленты, с которой работает [math]V[/math]. Заметим, что все конфигурации из [math]\Omega[/math] будут переданы [math]V[/math] с равными вероятностями. Теперь рассмотрим произвольную конфигурацию типа [math]\psi[/math] из [math]\Omega[/math], то есть конфигурацию, на которой [math]V[/math] допускает [math]\langle G_1, G_2 \rangle[/math]. Заметим, что для каждой такой конфигурации существует однозначно определяемая конфигурация типа [math]\overline \psi[/math], отличающаяся от [math]\psi[/math] только первым битом и также принадлежащая [math]\Omega[/math]. Запустившись на [math]\overline \psi[/math], [math]V[/math], очевидно, отвергнет [math]\langle G_1, G_2 \rangle[/math]. Таким образом, конфигураций типа [math]\psi[/math] в [math]\Omega[/math] не больше половины. Как уже отмечалось, конфигурации из [math]\Omega[/math] подаются [math]V[/math] с равными вероятностями, а конфигураций не из [math]\Omega[/math], по определению, [math]V[/math] не подаётся. Таким образом, вероятность ошибки не превышает [math]\frac{1}{2}[/math].
[math]\triangleleft[/math]