Изменения

<tex>\mathrm{PCP}</tex>'''-системой'''(системой вероятностно проверяемых доказательств) с полнотой <tex>c(n)</tex> и обоснованностью <tex>s(n)</tex> над алфавитом <tex>\Sigma</tex> для языка <tex>L</tex>, где <tex>0 \le s(n) \le c(n) \le 1</tex>, называется пара верификатор <tex>V</tex> {{---}} [[Вероятностные вычисления. Вероятностная машина Тьюринга#Основные определения|вероятностная машина Тьюринга]] , имеющая доступ к цепочке доказательству <tex>\pi \in \Sigma^{*} : |\pi| \le 2^{poly(|input|)}</tex> {{---}} доказательствуцепочке из <tex>\Sigma^{*}</tex>, удовлетворяющая следующим свойствам:* '''Полнота''': если <tex>x \in L</tex>, то вероятность того, что <tex>P(V^{\pi}(</tex> допустит <tex>x)=1) \ge </tex>, не меньше <tex>c(n)</tex> для некоторой некоторого <tex>\pi</tex>.,* '''Обоснованность''': если <tex>x \notin L</tex>, то вероятность того, что <tex>P(V^{\pi}(</tex> допустит <tex>x)=1) \le </tex>, не больше <tex>s(n)</tex> для любой любого <tex>\pi</tex>.

'''Randomness complexity'''(вероятностной сложностью) <tex>r(n)</tex> верификатора <tex>V</tex> называется число случайных битов, которое он использует используемых за всё время работы со входом длины <tex>n</tex>.

'''Query complexity'''(запросовой запросной сложностью) <tex>q(n)</tex> верификатора <tex>V</tex> называется число запросов битов из <tex>\pi</tex>, которое он отсылает отсылаемых за всё время работы со входом длины <tex>n</tex>.

Верификатор <tex>V</tex> называется '''non-adaptive'''(неадаптивным), если при отправке запроса не использует ответы на предыдущие. Иными словами, его работа не изменится, если все свои запросы он отправит отправить одновременно.

Сложностный класс <tex>\mathrm{PCP}_{c(n), s(n)}[r(n), q(n)]</tex> является объединением {{---}} это объединение всех языков всех <tex>L</tex>, для которых существует <tex>\mathrm{PCP}</tex>-система над бинарным алфавитом с полнотой <tex>c(n)</tex> и обоснованностью <tex>s(n)</tex>, в которой неадаптивный верификатор <tex>V</tex> неадаптивный, работает за полиномиальное время и имеет вероятностную и запросовую запросную сложности соответственно <tex>r(n)</tex> и <tex>q(n)</tex>, а доказательства имеют экспоненциальную длину.<br/>Часто <tex>\mathrm{PCP}_{1, \frac{1}^1/{2}_2}[r(n), q(n)]</tex> обозначают как <tex>\mathrm{PCP}[r(n), q(n)]</tex>.

|statement = <tex>\mathrm{PCP}[0, 0]</tex> = <tex>\mathrm{PCP}[O(\log(n)), 0]</tex> = <tex>\mathrm{PCP}[0, O(\log(n))]</tex> = <tex>\mathrm{P}</tex>.

* <tex>\mathrm{PCP}[0, 0]</tex> = <tex>\mathrm{P}</tex>: вероятностная МТ не использует случайные биты и не обращается к доказательству, то есть является обычной детерминированной работает как детерминированная МТ, работающей работающая за полиномиальное время.* <tex>\mathrm{PCP}[O(\log(n)), 0]</tex> = <tex>\mathrm{P}</tex>: доступ к <tex>O(\log(n))</tex> случайных бит не меняет ситуации, так как все возможные строки битовые цепочки логарифмической длины детерминированная МТ может сгенерировать и проверить за полиномиальное время.* <tex>\mathrm{PCP}[0, O(\log(n))]</tex> = <tex>\mathrm{P}</tex>: так как доступа к случайным битам нет, доказательство <tex>\pi</tex> можно рассматривать как строку битовую цепочку логарифмической длины. Все возможные такие строки цепочки детерминированная МТ может сгенерировать и проверить за полиномиальное время.

|statement = <tex>\mathrm{PCP}[poly(n), 0]</tex> = <tex>\mathrm{coRP}</tex>.

Очевидно следует из [[Вероятностные вычисления. Вероятностная машина ТьюрингаКлассы RP и coRP#Вероятностные сложностные классыОпределения|Определение определения coRP]].

|statement = <tex>\mathrm{PCP}[0, poly(n)]</tex> = <tex>\mathrm{NP}</tex>.

Очевидно следует из [[Недетерминированные вычисленияКлассы_NP_и_Σ₁|определения Σ₁]]. Классы }}{{Теорема|id=pcp_th|about=[[PCP-теорема]]|statement=<tex>\mathrm{PCP}[log(n), O(1)] = \mathrm{NP}</tex>|proof=В одну сторону включение тривиально <tex>\mathrm{PCP}(\log n, 1) \subseteq \mathrm{NTIME}(2^{O(\log n)}) = NP и Σ₁#Классы </tex>. Обратное включение <tex>NP \subseteq \mathrm{PCP}(\log n, 1)</tex> нетривиально и Σ₁рассматривается в [[PCP-теорема |Определение Σ₁PCP-теореме]].

|statement = '''Graph Nonisomorphism(GNI)''' <tex>\in \mathrm{PCP}[poly(n), O(1)]</tex>.

<tex>G_1</tex> и <tex>G_2</tex> {{---}} графы на <tex>n</tex> вершинах. Требуется проверить, изоморфны неизоморфны ли они друг другу. <br/>

* <tex>\pi[k] = 0</tex> тогда и только тогда, когда граф номер <tex>k</tex> изоморфен <tex>G_1</tex> и <tex>G_2</tex>;,* <tex>\pi[k] = 1</tex> тогда и только тогда, когда граф номер <tex>k</tex> изоморфен <tex>G_1</tex> и неизоморфен <tex>G_2</tex>;,

if (// <tex>\pi[\#H]</tex> == i) { return 1; }

* '''Полнота''': если графы неизоморфны, то существует <tex>\pi</tex> такая, что всякий её символ равен 1 или 2 и задан корректно. Тогда на этой <tex>\pi</tex> верификатор всегда вернёт 1.;* '''Обоснованность''': если графы изоморфны, то благодаря случайному выбору фиксируем <tex>\pi</tex>. Пусть <tex>i\Omega</tex> {{---}} это множество всех конфигураций случайной ленты, с которой работает <tex>V</tex>. Заметим, что все конфигурации из <tex>\Omega</tex> будут переданы <tex>V</tex> с равными вероятностями. Теперь рассмотрим произвольную конфигурацию типа <tex>\psi</tex> из <tex>\Omega</tex>, то есть конфигурацию, на которой <tex>V</tex> допускает <tex>\langle G_1, G_2 \rangle</tex>. Заметим, что для каждой такой конфигурации существует однозначно определяемая конфигурация типа <tex>\overline \psi</tex>, отличающаяся от <tex>\psi</tex> только первым битом и также принадлежащая <tex>\Omega</tex>. Запустившись на <tex>\overline \psi</tex>, <tex>V</tex>, очевидно, отвергнет <tex>\langle G_1, G_2 \rangle</tex>. Таким образом, конфигураций типа <tex>\psi</tex> в <tex>\Omega</tex> не больше половины. Как уже отмечалось, конфигурации из <tex>\Omega</tex> подаются <tex>V</tex> с равными вероятностями, а конфигураций не из <tex>\Omega</tex>, по определению, <tex>V</tex> не подаётся. Таким образом, вероятность ошибки не превышает <tex>\frac{1}^1/{2}_2</tex>.