PCP-система

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

Определения

Определение:

-системой (системой вероятностно проверяемых доказательств) с полнотой и обоснованностью над алфавитом для языка , где , называется — вероятностная машина Тьюринга, имеющая доступ к цепочке — доказательству, удовлетворяющая следующим свойствам:

Полнота: если [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 (вероятностной сложностью) верификатора называется число случайных битов, используемых за всё время работы со входом длины .

Определение:

Query complexity (запросной сложностью) верификатора называется число запросов битов из , отсылаемых за всё время работы со входом длины .

Определение:

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

Определение:

Сложностный класс — это объединение всех языков, для которых существует -система над бинарным алфавитом с полнотой и обоснованностью , в которой неадаптивный верификатор работает за полиномиальное время и имеет вероятностную и запросную сложности соответственно и .
Часто обозначают как .

Свойства

Теорема:

= = = .

Доказательство:

[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] можно рассматривать как битовую цепочку логарифмической длины. Все возможные такие цепочки детерминированная МТ может сгенерировать и проверить за полиномиальное время.

Теорема:

= .

Доказательство:

Очевидно следует из определения coRP.

Теорема:

= .

Доказательство:

Очевидно следует из определения Σ₁.

Пример

Теорема:

Graph Nonisomorphism(GNI) .

Доказательство:

[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;
   }
   if ([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]{}^1/{}_2[/math].

PCP-система

Определения

Свойства

Пример

Навигация

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

Пространства имён

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты