Изменения
Новая страница: «==Определение== Классом '''PCP[r(n), q(n)]''' ('''PCP''' - Probabilistically Checkable Proof), где <tex>n</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>
2) <tex>\pi</tex> - некоторая строка, выступающая в качестве средства доказательства (аналогично P в [[Класс IP|интерактивном протоколе доказательства]]). Очевидно, ее длина не превосходит 2<sup>poly(x)</sup>, так как только к такому множеству позиций сможет обратиться <tex>V</tex>
3) <tex>V</tex> - [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]], обращающаяся к случайной ленте не более <tex>q(n)</tex> раз
4) <tex>V</tex> обращается к строке <tex>\pi</tex> не более <tex>r(n)</tex> раз
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>
Классом '''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>
2) <tex>\pi</tex> - некоторая строка, выступающая в качестве средства доказательства (аналогично P в [[Класс IP|интерактивном протоколе доказательства]]). Очевидно, ее длина не превосходит 2<sup>poly(x)</sup>, так как только к такому множеству позиций сможет обратиться <tex>V</tex>
3) <tex>V</tex> - [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]], обращающаяся к случайной ленте не более <tex>q(n)</tex> раз
4) <tex>V</tex> обращается к строке <tex>\pi</tex> не более <tex>r(n)</tex> раз
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>
