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

PCP-система

2017-02-12T10:38:31Z

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

[[Категория: Теория сложности]]
'''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 =
Очевидно следует из [[Классы RP и coRP#Определения|определения 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>.
}}

Протокол Голдвассер-Сипсера для оценки размера множества

2017-02-12T09:43:41Z

188.243.10.149: /* Описание протокола */

==Описание протокола==
Рассмотрим множество <tex>S \subseteq \left\{ 0, 1 \right\} ^m</tex>, для которого существует сертификат проверки на принадлежность. Протоколом Голдвассер-Сипсера является двухуровневый [[Интерактивные протоколы. Класс IP. Класс AM| интерактивный протокол]], в котором <tex>V</tex> старается принять множество <tex>S</tex>, если <tex>|S| \ge K</tex>, и отвергнуть, если <tex>|S| \le \frac{K}{2}</tex>.

Выберем <tex>k</tex> так, чтобы <tex>2^{k - 2} \le K \le 2^{k - 1}</tex>. Тогда протокол устроен следующим образом:

<tex>V:</tex> Отправляет <tex>P</tex> случайным образом выбранные <tex>h : \left\{ 0, 1 \right\} ^ m \rightarrow \left\{ 0, 1 \right\} ^ k</tex> из [[Семейство универсальных попарно независимых хеш-функций| семейства универсальных попарно независимых хеш-функций]] <tex>H_{m, k}</tex> и <tex>y</tex> из <tex>\left\{ 0, 1 \right\} ^ k</tex>.

<tex>P:</tex> Пытается найти <tex>x \in S</tex>, такой что <tex>h(x) = y</tex>. Отправляет <tex>V</tex> найденный <tex>x</tex> и сертификат <tex>c</tex>, подтверждающий принадлежность <tex>x</tex> множеству <tex>S</tex>.

<tex>V:</tex> Если верно, что <tex>x \in S</tex> и <tex>h(x) = y</tex>, то множество <tex>S</tex> принимается. В противном случае <tex>V</tex> отвергает множество <tex>S</tex>.

==Оценки вероятностей==
Пусть <tex>p = \frac{K}{2^k}</tex>. Если <tex>|S| \le \frac{K}{2}</tex>, тогда <tex>|h(S)| \le \frac{p\cdot2^k}{2}</tex>. Отсюда получаем, что <tex>P[y \in h(S)] \le \frac{p}{2}</tex>. Необходимо показать, что в случае <tex>|S| \ge K</tex>, <tex>V</tex> будет принимать <tex>S</tex> с вероятностью различимо большей <tex>\frac{p}{2}</tex>.

{{Утверждение
|statement=
Если <tex>K \le |S| \le 2^{k - 1}</tex>, то <tex>P[\exists x \in S \bigm| h(x) = y] \ge \frac{3}{4}\cdot\frac{|S|}{2^k}</tex>, где <tex>h</tex> случайным образом выбрано из <tex>H_{m, k}</tex>, а <tex>y~-</tex> из <tex>\left\{0,1\right\}^k</tex>.
|proof=
Покажем, что для каждого <tex>y \in \left\{0,1\right\}^k</tex> и случайно выбранной функции <tex>h \in H_{m,k}</tex> справедливо <tex>P[\exists x \in S \bigm| h(x) = y] \ge \frac{3}{4} p</tex>.

Для каждого <tex>x \in S</tex> определим [[Вероятностное пространство, элементарный исход, событие|событие]] <tex>E_x = \left\{h \in H_{m, k} \bigm| h(x) = y\right\}</tex>. Тогда <tex>P[\exists x \in S \bigm| h(x) = y] = P[\bigcup \limits_{x \in S}E_x]</tex>, что [[Формула включения-исключения | формуле включения-исключения]] не меньше, чем <tex>\sum \limits_{x \in S}P[E_x] - \sum\limits_{x_1 \ne x_2 \in S}P[E_{x_1} \cap E_{x_2}]</tex>. Поскольку выбирались <tex>h \in H_{m, k}</tex>, то <tex>P[E_x] = \frac{1}{2^k}</tex> и <tex>P[E_{x_1} \cap E_{x_2}] = \frac{1}{2^{2k}}</tex>. Тогда <tex>P[\bigcup \limits_{x \in S}E_x] \ge \frac{|S|}{2^k} - \frac{1}{2}\cdot\frac{|S|^2}{2^{2k}} \ge \frac{3}{4}\cdot\frac{|S|}{2^k} \ge \frac{3}{4}p</tex>.
}}
Стоит отметить, что если <tex>|S| > 2^{k - 1}</tex>, то <tex>P</tex> может выбрать <tex>C \subseteq S</tex> так, чтобы <tex>K \le |C| \le 2^{k - 1}</tex>. А значит, в качестве нижней оценки <tex>P[\exists x \in S \bigm| h(x) = y]</tex> в этом случае можно использовать <tex>\frac{3}{4}p</tex>.

Итого:
# если <tex>|S| \le \frac{K}{2}</tex>, то <tex>P[V(|S| \ge K) = 1] \le \frac{p}{2}</tex>.
# если <tex>|S| \ge K</tex>, то <tex>P[V(|S| \ge K) = 1] \ge \frac{3}{4}p</tex>.

==Источники==
* ''Sanjeev Arora, Boaz Barak''. [http://www.cs.princeton.edu/theory/complexity Computational Complexity: A Modern Approach]

[[Категория: Теория сложности]]