Класс PCP

Определение

Классом PCP[r(n), q(n)] (PCP - Probabilistically Checkable Proof), где [math]n[/math] - длина входного слова, называется множество языков, распознаваемых машиной [math]V^{\pi}(x)[/math], обладающей следующими свойствами:

1. Время работы [math]V^{\pi}(x)[/math] ограничено сверху некоторым полиномом от длины [math]x[/math].
2. [math]\pi[/math] - некоторая строка, выступающая в качестве средства доказательства (аналогично P в интерактивном протоколе доказательства). Очевидно, ее длина не превосходит 2^poly(x), так как только к такому множеству позиций сможет обратиться [math]V[/math].
3. [math]V[/math] - вероятностная машина Тьюринга, обращающаяся к случайной ленте не более [math]r(n)[/math] раз.
4. [math]V[/math] обращается к строке [math]\pi[/math] не более [math]q(n)[/math] раз.
5. [math]x \in L \Rightarrow \exists \pi : Pr(V^{\pi}(x)=1)=1 \ [/math] , где [math]Pr(V^{\pi}(x)=1)[/math] - вероятность того, что [math]V[/math] допустит [math]x[/math].
6. [math]\ x \notin L \Rightarrow \forall \pi : Pr(V^{\pi}(x)=1)\le \frac{1}{2} [/math].

Можно считать, что строка [math]\pi[/math] всегда такая, что пытается убедить [math]V[/math] с максимальной вероятностью принять [math]x[/math]. Если [math]x \in L [/math], то это происходить с вероятностью 1, иначе с вероятностью не более [math] \frac{1}{2} [/math].

Свойства

1. PCP[0, 0] = P (по определению P - нет случайности и обращений к [math]\pi[/math])
2. PCP[log(n), 0] = P (логарифмическое число обращений к случайной ленте не помогают, так как можно за полиномиальное время перебрать всевозможные результаты обращений)
3. PCP[0, log(n)] = P (логарифмическое число обращений к строке [math]\pi[/math] также не помогают, так как можно аналогичным образом перебрать всевозможные результаты обращений за полиномиальное время)
4. PCP[poly(n), 0] = coRP (по определению coRP)
5. PCP[0, poly(n)] = NP (по определению NP на языке сертификатов)
6. PCP[log(n), O(1)] = NP (PCP-теорема)

Теорема

GNI ∈ PCP[poly(n), O(1)]

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

Алгоритм работы машины [math]V[/math] аналогичен алгоритму работы при доказательстве того, что GNI ∈ IP.

В строке [math]\pi[/math] для каждого графа (введена некоторая нумерация графов) записано, кому из данных графов [math]G_1, G_2[/math] он изоморфен.

1. [math]V[/math] случайным образом выбирает число [math]i = rand(2)[/math].
2. [math]V[/math] строит новый граф [math]F[/math], изоморфный графу [math]G_i[/math], перенумеровав в нём вершины случайным образом.
3. [math]V[/math] смотрит в [math]\pi[/math] кому граф [math]F[/math] изоморфен, пусть это [math]j[/math]
4. [math]V[/math] возвращает 1, если [math]j = i[/math], и 0 в противном случае.

В случае, если графы неизоморфны, то в [math]\pi[/math] для каждого графа однозначно определено, кому он изоморфен и потому, посмотрев на позицию соответствующую графу [math]f[/math], [math]V[/math] точно получит [math]j = i[/math].

Если же графы изоморфны, то полученное [math]j[/math] может быть равновероятно равно [math]1[/math] или [math]2[/math], потому вероятность "обмана" [math]V[/math] равна [math]\frac{1}{2}[/math].