Викиконспекты - Вклад участника [ru]

PCP-система

2015-06-11T13:51:15Z

95.55.113.66: /* Свойства */

[[Категория: Теория сложности]]
'''PCP(probabilistically checkable proof)''' - вид доказательства, проверяемого рандомизированным алгоритмом, использующим ограниченное число случайных бит и читающим ограниченное число бит доказательства. Такой алгоритм должен с достаточно высокими вероятностями принимать корректные доказательства и отвергать ошибочные.

== Определения ==
{{Определение
|definition =
<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</tex> {{---}} цепочке из <tex>\Sigma^{*}</tex>, удовлетворяющая следующим свойствам:
* '''Полнота''': если <tex>x \in L</tex>, то вероятность того, что <tex>V^{\pi}</tex> допустит <tex>x</tex>, не меньше <tex>c(n)</tex> для некоторого <tex>\pi</tex>,
* '''Обоснованность''': если <tex>x \notin L</tex>, то вероятность того, что <tex>V^{\pi}</tex> допустит <tex>x</tex>, не больше <tex>s(n)</tex> для любого <tex>\pi</tex>.
}}
{{Определение
|definition =
'''Randomness complexity''' (вероятностной сложностью) <tex>r(n)</tex> верификатора <tex>V</tex> называется число случайных битов, используемых за всё время работы со входом длины <tex>n</tex>.
}}
{{Определение
|definition =
'''Query complexity''' (запросной сложностью) <tex>q(n)</tex> верификатора <tex>V</tex> называется число запросов битов из <tex>\pi</tex>, отсылаемых за всё время работы со входом длины <tex>n</tex>.
}}
{{Определение
|definition =
Верификатор <tex>V</tex> называется '''non-adaptive''' (неадаптивным), если при отправке запроса не использует ответы на предыдущие. Иными словами, его работа не изменится, если все запросы отправить одновременно.
}}
{{Определение
|definition =
Сложностный класс <tex>\mathrm{PCP}_{c(n), s(n)}[r(n), q(n)]</tex> {{---}} это объединение всех языков, для которых существует <tex>\mathrm{PCP}</tex>-система над бинарным алфавитом с полнотой <tex>c(n)</tex> и обоснованностью <tex>s(n)</tex>, в которой неадаптивный верификатор <tex>V</tex> работает за полиномиальное время и имеет вероятностную и запросную сложности соответственно <tex>r(n)</tex> и <tex>q(n)</tex>, а доказательства имеют экспоненциальную длину. 
Часто <tex>\mathrm{PCP}_{1, \frac{1}{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>.
|proof =
* <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>.
|proof =
Очевидно следует из [[Вероятностные вычисления. Вероятностная машина Тьюринга#Вероятностные сложностные классы|определения coRP]].
}}
{{Теорема
|statement = <tex>\mathrm{PCP}[0, poly(n)]</tex> = <tex>\mathrm{NP}</tex>.
|proof =
Очевидно следует из [[Классы_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>.
|proof =
<tex>G_1</tex> и <tex>G_2</tex> {{---}} графы на <tex>n</tex> вершинах. Требуется проверить, неизоморфны ли они друг другу. 
Сперва пронумеруем все возможные графы на <tex>n</tex> вершинах. Не умаляя общности, будем считать, что <tex>\pi</tex> над троичным алфавитом. 
Будем считать корректной <tex>\pi</tex>: 
* <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>,
* <tex>\pi[k] = 2</tex> тогда и только тогда, когда граф номер <tex>k</tex> неизоморфен <tex>G_1</tex> и изоморфен <tex>G_2</tex>.
Верификатором <tex>V</tex> будет вероятностная МТ, работающая эквивалентно следующему псевдокоду: 
p(<tex>\langle G_1, G_2 \rangle</tex>) {
i = random{1, 2};
<tex>\phi</tex> = random permutation{1..n};
<tex>H</tex> = <tex>\phi(G_i)</tex>;
if (<tex>\pi[\#H]</tex> == 0) or (<tex>\pi[\#H]</tex> == 3-i) {
return 0;
}
// <tex>\pi[\#H]</tex> == i
return 1;
}
Проверим полноту и обоснованность:
* '''Полнота''': если графы неизоморфны, то существует <tex>\pi</tex> такая, что всякий её символ равен 1 или 2 и задан корректно. Тогда на этой <tex>\pi</tex> верификатор всегда вернёт 1;
* '''Обоснованность''': если графы изоморфны, то фиксируем <tex>\pi</tex>. Пусть <tex>\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}{2}</tex>.
}}

PCP-система

2015-06-10T19:42:28Z

95.55.113.66: /* Свойства */

[[Категория: Теория сложности]]
'''PCP(probabilistically checkable proof)''' - вид доказательства, проверяемого рандомизированным алгоритмом, использующим ограниченное число случайных бит и читающим ограниченное число бит доказательства. Такой алгоритм должен с достаточно высокими вероятностями принимать корректные доказательства и отвергать ошибочные.

== Определения ==
{{Определение
|definition =
<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</tex> {{---}} цепочке из <tex>\Sigma^{*}</tex>, удовлетворяющая следующим свойствам:
* '''Полнота''': если <tex>x \in L</tex>, то вероятность того, что <tex>V^{\pi}</tex> допустит <tex>x</tex>, не меньше <tex>c(n)</tex> для некоторого <tex>\pi</tex>,
* '''Обоснованность''': если <tex>x \notin L</tex>, то вероятность того, что <tex>V^{\pi}</tex> допустит <tex>x</tex>, не больше <tex>s(n)</tex> для любого <tex>\pi</tex>.
}}
{{Определение
|definition =
'''Randomness complexity''' (вероятностной сложностью) <tex>r(n)</tex> верификатора <tex>V</tex> называется число случайных битов, используемых за всё время работы со входом длины <tex>n</tex>.
}}
{{Определение
|definition =
'''Query complexity''' (запросной сложностью) <tex>q(n)</tex> верификатора <tex>V</tex> называется число запросов битов из <tex>\pi</tex>, отсылаемых за всё время работы со входом длины <tex>n</tex>.
}}
{{Определение
|definition =
Верификатор <tex>V</tex> называется '''non-adaptive''' (неадаптивным), если при отправке запроса не использует ответы на предыдущие. Иными словами, его работа не изменится, если все запросы отправить одновременно.
}}
{{Определение
|definition =
Сложностный класс <tex>\mathrm{PCP}_{c(n), s(n)}[r(n), q(n)]</tex> {{---}} это объединение всех языков, для которых существует <tex>\mathrm{PCP}</tex>-система над бинарным алфавитом с полнотой <tex>c(n)</tex> и обоснованностью <tex>s(n)</tex>, в которой неадаптивный верификатор <tex>V</tex> работает за полиномиальное время и имеет вероятностную и запросную сложности соответственно <tex>r(n)</tex> и <tex>q(n)</tex>, а доказательства имеют экспоненциальную длину. 
Часто <tex>\mathrm{PCP}_{1, \frac{1}{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>.
|proof =
* <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>.
|proof =
TODO: По-моему, бред и равен <tex>\mathrm{BPP}</tex>, т.к. ошибка как минимум, двухсторонняя.

Очевидно следует из [[Вероятностные вычисления. Вероятностная машина Тьюринга#Вероятностные сложностные классы|определения coRP]].
}}
{{Теорема
|statement = <tex>\mathrm{PCP}[0, poly(n)]</tex> = <tex>\mathrm{NP}</tex>.
|proof =
Очевидно следует из [[Классы_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>.
|proof =
<tex>G_1</tex> и <tex>G_2</tex> {{---}} графы на <tex>n</tex> вершинах. Требуется проверить, неизоморфны ли они друг другу. 
Сперва пронумеруем все возможные графы на <tex>n</tex> вершинах. Не умаляя общности, будем считать, что <tex>\pi</tex> над троичным алфавитом. 
Будем считать корректной <tex>\pi</tex>: 
* <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>,
* <tex>\pi[k] = 2</tex> тогда и только тогда, когда граф номер <tex>k</tex> неизоморфен <tex>G_1</tex> и изоморфен <tex>G_2</tex>.
Верификатором <tex>V</tex> будет вероятностная МТ, работающая эквивалентно следующему псевдокоду: 
p(<tex>\langle G_1, G_2 \rangle</tex>) {
i = random{1, 2};
<tex>\phi</tex> = random permutation{1..n};
<tex>H</tex> = <tex>\phi(G_i)</tex>;
if (<tex>\pi[\#H]</tex> == 0) or (<tex>\pi[\#H]</tex> == 3-i) {
return 0;
}
// <tex>\pi[\#H]</tex> == i
return 1;
}
Проверим полноту и обоснованность:
* '''Полнота''': если графы неизоморфны, то существует <tex>\pi</tex> такая, что всякий её символ равен 1 или 2 и задан корректно. Тогда на этой <tex>\pi</tex> верификатор всегда вернёт 1;
* '''Обоснованность''': если графы изоморфны, то фиксируем <tex>\pi</tex>. Пусть <tex>\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}{2}</tex>.
}}