Класс PCP — различия между версиями

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

Текущая версия на 19:25, 4 сентября 2022

Определение

Классом 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 в интерактивном протоколе доказательства). Очевидно, ее длина не превосходит 2poly(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] = co-RP (по определению co-RP)
  5. PCP[0, poly(n)] = NP (по определению NP на языке сертификатов)
  6. PCP[log(n), O(1)] = NP (PCP-теорема)

Пример

GNIPCP[poly(n), O(1)]

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

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

В строке [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].

Дополнительные материалы

  • [1] Wikipedia - The Free Encyclopedia