1632
правки
Изменения
м
1) # Время работы <tex>V^{\pi}(x)</tex> ограничено сверху некоторым полиномом от длины <tex>x</tex>.# <tex>\pi</tex> - некоторая строка, выступающая в качестве средства доказательства (аналогично P в [[Класс IP|интерактивном протоколе доказательства]]). Очевидно, ее длина не превосходит 2<sup>poly(x)</sup>, так как только к такому множеству позиций сможет обратиться <tex>V</tex>.# <tex>V</tex> - [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]], обращающаяся к случайной ленте не более <tex>r(n)</tex> раз.# <tex>V</tex> обращается к строке <tex>\pi</tex> не более <tex>q(n)</tex> раз.# <tex>x \in L \Rightarrow \exists \pi : Pr(V^{\pi}(x)=1)=1 \ </tex> , где <tex>Pr(V^{\pi}(x)=1)</tex> - вероятность того, что <tex>V</tex> допустит <tex>x</tex>.# <tex>\ x \notin L \Rightarrow \forall \pi : Pr(V^{\pi}(x)=1)\le \frac{1}{2} </tex>.
2) Можно считать, что строка <tex>\pi</tex> - некоторая строкавсегда такая, выступающая в качестве средства доказательства (аналогично P в [[Класс IP|интерактивном протоколе доказательства]])что пытается убедить <tex>V</tex> с максимальной вероятностью принять <tex>x</tex>. Очевидно, ее длина не превосходит 2Если <suptex>poly(x)\in L </suptex>, так как только к такому множеству позиций сможет обратиться то это происходит с вероятностью 1, иначе с вероятностью не более <tex>V\frac{1}{2} </tex>.
3) <tex>V</tex> - [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]], обращающаяся к случайной ленте не более <tex>q(n)</tex> раз==Свойства==
4) # '''PCP'''[0, 0] = '''[[P]]''' (по определению '''P''' - нет случайности и обращений к <tex>V\pi</tex> обращается )# '''PCP'''[''log(n)'', 0] = '''P''' (логарифмическое число обращений к случайной ленте не помогают, так как можно за полиномиальное время перебрать всевозможные результаты обращений)# '''PCP'''[0, ''log(n)''] = '''P''' (логарифмическое число обращений к строке <tex>\pi</tex> также не более <tex>rпомогают, так как можно аналогичным образом перебрать всевозможные результаты обращений за полиномиальное время)# '''PCP'''[''poly(n)'', 0] = '''[[Сложностные_классы_RP_и_coRP|co-RP]]''' (по определению '''co-RP''')# '''PCP'''[0, ''poly(n)''] = '''[[NP]]''' (по определению '''NP''' на языке сертификатов)# '''PCP'''[''log(n)</tex> раз'', ''O''(1)] = '''NP''' ([[PCP-теорема]])
5) <tex>x \in L \Rightarrow \exists \pi : Pr(V^{\pi}(x)=1)=1 \ </tex> , где <tex>Pr(V^{\pi}(x)Пример==1)</tex> - вероятность того, что <tex>V</tex> допустит <tex>x</tex>
6'''[[GNI]]''' ∈ '''PCP[poly(n), O(1) ]''' ==Доказательство== Алгоритм работы машины <tex>V</tex> аналогичен алгоритму работы при доказательстве того, что '''[[GNI]]''' ∈ '''IP'''. В строке <tex>\ x \notin L \Rightarrow \forall pi</tex> для каждого графа (введена некоторая нумерация графов) записано, кому из данных графов <tex>G_1, G_2</tex> он изоморфен. # <tex>V</tex> случайным образом выбирает число <tex>i = rand(2)</tex>.# <tex>V</tex> строит новый граф <tex>F</tex>, изоморфный графу <tex>G_i</tex>, перенумеровав в нём вершины случайным образом.# <tex>V</tex> смотрит в <tex>\pi : Pr(</tex> кому граф <tex>F</tex> изоморфен, пусть это <tex>j</tex># <tex>V^{</tex> возвращает 1, если <tex>j = i</tex>, и 0 в противном случае. В случае, если графы неизоморфны, то в <tex>\pi}(x)</tex> для каждого графа однозначно определено, кому он изоморфен и потому, посмотрев на позицию соответствующую графу <tex>f</tex>, <tex>V</tex> точно получит <tex>j =i</tex>. Если же графы изоморфны, то полученное <tex>j</tex> может быть равновероятно равно <tex>1)\le </tex> или <tex>2</tex>, потому вероятность "обмана" <tex>V</tex> равна <tex>\frac{1}{2} </tex>. ==Дополнительные материалы==*[http://en.wikipedia.org/wiki/Probabilistically_checkable_proof] Wikipedia - The Free Encyclopedia
rollbackEdits.php mass rollback
Классом '''PCP[r(n), q(n)]''' ('''PCP''' - Probabilistically Checkable Proof), где <tex>n</tex> - длина входного слова, называется множество языков, распознаваемых машиной <tex>V^{\pi}(x)</tex>, обладающей следующими свойствами:
