1632
правки
Изменения
м
rollbackEdits.php mass rollback
# <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>.
Можно считать, что строка <tex>\pi</tex> всегда такая, что пытается убедить <tex>V</tex> с максимальной вероятностью принять <tex>x</tex>. Если <tex>x \in L </tex>, то это происходит с вероятностью 1, иначе с вероятностью не более <tex> \frac{1}{2} </tex>.
==Свойства==
# '''PCP'''[0, 0] = '''[[P|P]]''' (по определению '''P''' - нет случайности и обращений к <tex>\pi</tex>)# '''PCP'''[''log(n)'', 0] = [[P|'''P]]''' (логарифмическое число обращений к случайной ленте не помогают, так как можно за полиномиальное время перебрать всевозможные результаты обращений)# '''PCP'''[0, ''log(n)''] = [[P|'''P]]''' (логарифмическое число обращений к строке <tex>\pi</tex> также не помогают, так как можно аналогичным образом перебрать всевозможные результаты обращений за полиномиальное время)# '''PCP'''[''poly(n)'', 0] = '''[[Сложностные_классы_RP_и_coRP|coRPco-RP]]''' (по определению '''coRPco-RP''')# '''PCP'''[0, ''poly(n)''] = '''[[NP|NP]]''' (по определению '''NP''' на языке сертификатов)# '''PCP'''[''log(n)'', ''O''(1)] = [['''NP|NP]]''' ([[PCP-теорема]])
==ТеоремаПример==
'''[[GNI]]''' ∈ '''PCP[poly(n), O(1)]'''
==Доказательство==
Алгоритм работы машины '''<tex>V''' </tex> аналогичен алгоритму работы при доказательстве того, что '''[[GNI]]''' ∈ '''IP'''.
В строке <tex>\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</tex> кому граф <tex>F</tex> изоморфен, пусть это <tex>j</tex>
# <tex>V</tex> возвращает 1, если <tex>j = i</tex>, и 0 в противном случае.
В случае, если графы неизоморфны, то в <tex>\pi</tex> для каждого графа однозначно определено, кому он изоморфен и потому, посмотрев на позицию соответствующую графу <tex>f</tex>, <tex>V</tex> точно получит <tex>j = i</tex>.
Если же графы изоморфны, то полученное <tex>j</tex> может быть равновероятно равно <tex>1</tex> или <tex>2</tex>, потому вероятность "обмана" <tex>V</tex> равна <tex>\frac{1}{2}</tex>.
==Дополнительные материалы==
*[http://en.wikipedia.org/wiki/Probabilistically_checkable_proof] Wikipedia - The Free Encyclopedia
