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