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]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]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]\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] |
Пример
| Теорема: |
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;
}
if ([math]\pi[\#H][/math] == i) {
return 1;
}
}
Проверим полноту и обоснованность:
- Полнота: если графы неизоморфны, то существует [math]\pi[/math] такая, что всякий её символ равен 1 или 2 и задан корректно. Тогда на этой [math]\pi[/math] верификатор всегда вернёт 1;
- Обоснованность: если графы изоморфны, то благодаря случайному выбору [math]i[/math] вероятность ошибки не превышает [math]{}^1/{}_2[/math].
|
| [math]\triangleleft[/math] |
