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

Материал из Викиконспекты
Перейти к: навигация, поиск
(доказательство PCP)
(Графы условий)
 
(не показано 18 промежуточных версий 3 участников)
Строка 2: Строка 2:
 
|id=pcp_th
 
|id=pcp_th
 
|about=<tex>\mathrm{PCP}</tex> теорема
 
|about=<tex>\mathrm{PCP}</tex> теорема
|statement=<tex>\mathrm{PCP}[log(n), O(1)] = \mathrm{NP}</tex>
+
|statement=<tex>\mathrm{PCP}[\log n, O(1)] = \mathrm{NP}</tex>
 
}}
 
}}
  
 
Классическое доказательство [[Класс PCP|<tex>\mathrm{PCP}</tex>]] теоремы громоздкое и довольно сложное для восприятия,  
 
Классическое доказательство [[Класс PCP|<tex>\mathrm{PCP}</tex>]] теоремы громоздкое и довольно сложное для восприятия,  
рассмотрим вариант докаательства, предложенный Динуром.
+
рассмотрим вариант докаательства, предложенный Динур. Оно основано на том, что <tex>\mathrm{PCP}</tex>-теорема [[Эквивалентность_PCP-теоремы_и_теоремы_о_трудности_аппроксимации | эквивалентна <tex>\mathrm{NP}</tex>-трудности задачи <tex>\rho-GAPqCSP</tex>]].
 
+
<!--
 
==Лемма об эквивалентности PCP теоремы и NP-трудности GAP-3SAT==
 
==Лемма об эквивалентности PCP теоремы и NP-трудности GAP-3SAT==
  
Строка 26: Строка 26:
 
Сначала докажем, что из <tex>\mathrm{PCP}</tex> теоремы следует <tex>\mathrm{NP}</tex>-трудность <tex>GAP-3SAT_s</tex>.
 
Сначала докажем, что из <tex>\mathrm{PCP}</tex> теоремы следует <tex>\mathrm{NP}</tex>-трудность <tex>GAP-3SAT_s</tex>.
  
Заметим, что для <tex>\mathrm{NP}</tex>-полной задачи <tex>3-Color</tex> существует сведение <tex>\mathcal{R}</tex> к <tex>GAP-3SAT_s</tex>.
+
Покажем, что для <tex>\mathrm{NP}</tex>-полной задачи <tex>3-Color</tex> существует сведение <tex>\mathcal{R}</tex> к <tex>GAP-3SAT_s</tex>.
  
 
Из принадлежности <tex>3Color</tex> <tex>\mathrm{NP}</tex> и <tex>\mathrm{PCP}</tex> теоремы следует, что существует  
 
Из принадлежности <tex>3Color</tex> <tex>\mathrm{NP}</tex> и <tex>\mathrm{PCP}</tex> теоремы следует, что существует  
 
доказательство <tex>\pi</tex> прувера <tex>\mathcal{P}</tex>. Обозначим <tex>\pi_i</tex> <tex>i</tex>-й бит доказательства (не его значение), будем рассматривать <tex>\pi_i</tex> как переменные в <tex>3SAT</tex> формуле.
 
доказательство <tex>\pi</tex> прувера <tex>\mathcal{P}</tex>. Обозначим <tex>\pi_i</tex> <tex>i</tex>-й бит доказательства (не его значение), будем рассматривать <tex>\pi_i</tex> как переменные в <tex>3SAT</tex> формуле.
  
По данному графу <tex>G</tex>, <tex>\mathcal{R}</tex> нумерует все <tex>N = 2^Q = 2^{O(log(n)} = poly(n)</tex> возможные
+
По данному графу <tex>G</tex>, <tex>\mathcal{R}</tex> нумерует все <tex>N = 2^Q = 2^{O(\log n} = poly(n)</tex> возможные
 
случайные строки, которые может выбрать верифаер <tex>V</tex>. Обозначим их <tex>Q_1 ... Q_{poly(n)}</tex>.
 
случайные строки, которые может выбрать верифаер <tex>V</tex>. Обозначим их <tex>Q_1 ... Q_{poly(n)}</tex>.
  
 
Каждая строка <tex>Q_i</tex> дает нам <tex>C</tex> позиций в доказательстве и предикат <tex>\phi</tex>. <tex>\mathcal{R}</tex>  
 
Каждая строка <tex>Q_i</tex> дает нам <tex>C</tex> позиций в доказательстве и предикат <tex>\phi</tex>. <tex>\mathcal{R}</tex>  
строит <tex>3CNF</tex> формулу для каждого <tex>\phi</tex>. Поскольку <tex>\phi</tex> функция от </tex>C</tex> пременных,
+
строит <tex>3CNF</tex> формулу для каждого <tex>\phi</tex>. Поскольку <tex>\phi</tex> функция от <tex>C</tex> пременных,
 
построенная <tex>3CNF</tex> содержит не более <tex>K=C2^C</tex> дизъюнктов. Для упрощения будем считать, что формула содержит  
 
построенная <tex>3CNF</tex> содержит не более <tex>K=C2^C</tex> дизъюнктов. Для упрощения будем считать, что формула содержит  
 
<tex>K</tex> дизъюнктов. <tex>\mathcal{R}</tex> возвращает конъюнкцию всех полученных формул, содержащую <tex>m=NK</tex> дизъюнктов.
 
<tex>K</tex> дизъюнктов. <tex>\mathcal{R}</tex> возвращает конъюнкцию всех полученных формул, содержащую <tex>m=NK</tex> дизъюнктов.
Строка 68: Строка 68:
 
Таким образом мы показали эвивалентность <tex>\mathrm{PCP}</tex> теоремы вопросу <tex>\mathrm{NP}</tex>-трудности задачи <tex>GAP-3SAT_s</tex>.
 
Таким образом мы показали эвивалентность <tex>\mathrm{PCP}</tex> теоремы вопросу <tex>\mathrm{NP}</tex>-трудности задачи <tex>GAP-3SAT_s</tex>.
 
}}
 
}}
 
+
!-->
 
==Определения и леммы, используемые в доказательстве==
 
==Определения и леммы, используемые в доказательстве==
 
{{Определение
 
{{Определение
Строка 83: Строка 83:
 
|definition=
 
|definition=
 
<tex>G=\left\langle(V,E,\Sigma,\mathcal{C}\right\rangle</tex> называется графом условий, если:
 
<tex>G=\left\langle(V,E,\Sigma,\mathcal{C}\right\rangle</tex> называется графом условий, если:
* <tex>(V,E)</tex> &mdash; неориентированный граф, называемый графом, леащим в основе <tex>G</tex>.
+
* <tex>(V,E)</tex> &mdash; неориентированный граф, называемый графом, лежащим в основе <tex>G</tex>.
 
* Множество <tex>V</tex> также представляется в виде множества переменных принимающих значениями из алфавита <tex>\Sigma</tex>
 
* Множество <tex>V</tex> также представляется в виде множества переменных принимающих значениями из алфавита <tex>\Sigma</tex>
 
* Каждое ребро <tex>e \in E</tex> содержит условие <tex>c(e) \subseteq \Sigma^2</tex> и <tex>\mathcal{C}=\lbrace c(e)\rbrace_{e \in E}</tex>. Условие <tex>c(e)</tex> называется удовлетворенным парой <tex>(a, b)</tex>, если <tex>(a, b) \in c(e)</tex>
 
* Каждое ребро <tex>e \in E</tex> содержит условие <tex>c(e) \subseteq \Sigma^2</tex> и <tex>\mathcal{C}=\lbrace c(e)\rbrace_{e \in E}</tex>. Условие <tex>c(e)</tex> называется удовлетворенным парой <tex>(a, b)</tex>, если <tex>(a, b) \in c(e)</tex>
Строка 110: Строка 110:
 
|about=О экспандерах
 
|about=О экспандерах
 
|statement=Существует <tex>d_0 \in \mathbb{N}</tex> и  <tex>h_0 >0</tex> такие, что есть построимое за полиномиальное время семейство <tex>\lbrace X_n\rbrace_{n \in \mathbb{N}}</tex> <tex>d_0</tex>-регулярных графов <tex>X_n</tex> с <tex>n</tex> вершинами таких, что <tex>h(X_n) \ge h_0</tex>.
 
|statement=Существует <tex>d_0 \in \mathbb{N}</tex> и  <tex>h_0 >0</tex> такие, что есть построимое за полиномиальное время семейство <tex>\lbrace X_n\rbrace_{n \in \mathbb{N}}</tex> <tex>d_0</tex>-регулярных графов <tex>X_n</tex> с <tex>n</tex> вершинами таких, что <tex>h(X_n) \ge h_0</tex>.
|proof=TODO
+
|proof=см. [http://eccc.hpi-web.de/report/2005/046 The PCP Theorem by Gap Amplification, Irit Dinur, 2005]
 
}}
 
}}
  
Строка 123: Строка 123:
 
{{Лемма
 
{{Лемма
 
|statement=Пусть <tex>G</tex> <tex>d</tex>-регулярный граф со вторым по величине собственным числом <tex>\lambda</tex>. Пусть <tex>F \subseteq E</tex> множество ребер. Вероятность <tex>p</tex> того, что случайный путь, начинающийся со случайного ребра из <tex>F</tex> на <tex>i+1</tex> шаге попадет <tex>F</tex> ограничена <tex>\frac {|F|} {|E|} + \left({\frac {|\lambda|} d}\right)^i</tex>.
 
|statement=Пусть <tex>G</tex> <tex>d</tex>-регулярный граф со вторым по величине собственным числом <tex>\lambda</tex>. Пусть <tex>F \subseteq E</tex> множество ребер. Вероятность <tex>p</tex> того, что случайный путь, начинающийся со случайного ребра из <tex>F</tex> на <tex>i+1</tex> шаге попадет <tex>F</tex> ограничена <tex>\frac {|F|} {|E|} + \left({\frac {|\lambda|} d}\right)^i</tex>.
|proof=TODO
+
|proof=см. [http://eccc.hpi-web.de/report/2005/046 The PCP Theorem by Gap Amplification, Irit Dinur, 2005]
 
}}
 
}}
 
+
<!--
 
===Вероятности===
 
===Вероятности===
 
Следующее неравенство в стиле неравенства Чебышева удобно использовать, чтобы показать что для неотрицательной случайной величины <tex>X</tex>, <tex>Pr[X > 0] \approx \mathbb{E}[X]</tex> когда <tex>\mathbb{E}[X] \approx \mathbb{E}[X^2]</tex>.
 
Следующее неравенство в стиле неравенства Чебышева удобно использовать, чтобы показать что для неотрицательной случайной величины <tex>X</tex>, <tex>Pr[X > 0] \approx \mathbb{E}[X]</tex> когда <tex>\mathbb{E}[X] \approx \mathbb{E}[X^2]</tex>.
Строка 131: Строка 131:
 
{{Утверждение
 
{{Утверждение
 
|statement= Для любой неотрицательной случайной величины <tex>X</tex>, <tex>Pr[X>0] \ge \mathbb{E}[X^2] / \mathbb{E}[X]</tex>
 
|statement= Для любой неотрицательной случайной величины <tex>X</tex>, <tex>Pr[X>0] \ge \mathbb{E}[X^2] / \mathbb{E}[X]</tex>
|proof=TODO
+
|proof=см. [http://eccc.hpi-web.de/report/2005/046 The PCP Theorem by Gap Amplification, Irit Dinur, 2005]
 
}}
 
}}
  
 
===Коды с коррекцией ошибок===
 
===Коды с коррекцией ошибок===
 
{{Определение
 
{{Определение
|definition=Кодом с коррекцией ошибок называется набор строк <tex>C \subset \Sigma^n</tex>, где <tex>\Sigma</tex> некоторый конечный алфавит. <tex>n</tex> называется размером блока, а <tex>log_{|\Sigma|}|C|</tex> уровнем кода. Расстоянием кода называется <tex>min_{x \neq y \in C} dist(x,y)</tex>, где <tex>dist(\cdot,\cdot)</tex> &mdash; расстояние Хэмминга.
+
|definition=Кодом с коррекцией ошибок называется набор строк <tex>C \subset \Sigma^n</tex>, где <tex>\Sigma</tex> некоторый конечный алфавит. <tex>n</tex> называется размером блока, а <tex>\log_{|\Sigma|}|C|</tex> уровнем кода. Расстоянием кода называется <tex>min_{x \neq y \in C} dist(x,y)</tex>, где <tex>dist(\cdot,\cdot)</tex> &mdash; расстояние Хэмминга.
 
}}
 
}}
  
Строка 142: Строка 142:
  
 
Известно, что существуют семейства кодов <tex>\lbrace C_n \subset \lbrace 0,1 \rbrace^n \rbrace_{n \in \mathbb{N}}</tex>, для которых уровень и расстояние равны <tex>O(n)</tex> и существует схема полиномиального размера, проверяющая <tex>x \in C_n</tex>.
 
Известно, что существуют семейства кодов <tex>\lbrace C_n \subset \lbrace 0,1 \rbrace^n \rbrace_{n \in \mathbb{N}}</tex>, для которых уровень и расстояние равны <tex>O(n)</tex> и существует схема полиномиального размера, проверяющая <tex>x \in C_n</tex>.
 +
!-->
  
 
==Операции на графах условий==
 
==Операции на графах условий==
Строка 164: Строка 165:
 
|about=Константная степень
 
|about=Константная степень
 
|statement=Любой граф условий <tex>G = \langle (V,E),\Sigma,\mathcal{C}\rangle</tex> может быть преобразован в <tex>(d_0 + 1)</tex>-регулярный граф условий <tex>G'=\langle (V',E'),\Sigma,\mathcal{C}'\rangle</tex> такой, что <tex>|V'|</tex>=2|E|</tex> и <tex>c \cdot UNSAT(G) \le UNSAT(G') \le UNSAT(G)</tex>. Для некоторых заданных констант <tex>d_0,c>0</tex>
 
|statement=Любой граф условий <tex>G = \langle (V,E),\Sigma,\mathcal{C}\rangle</tex> может быть преобразован в <tex>(d_0 + 1)</tex>-регулярный граф условий <tex>G'=\langle (V',E'),\Sigma,\mathcal{C}'\rangle</tex> такой, что <tex>|V'|</tex>=2|E|</tex> и <tex>c \cdot UNSAT(G) \le UNSAT(G') \le UNSAT(G)</tex>. Для некоторых заданных констант <tex>d_0,c>0</tex>
|proof=TODO
+
|proof=см. [http://eccc.hpi-web.de/report/2005/046 The PCP Theorem by Gap Amplification, Irit Dinur, 2005]
 
}}
 
}}
  
Строка 176: Строка 177:
 
* <tex>size(G')=O(size(G))</tex>
 
* <tex>size(G')=O(size(G))</tex>
 
* <tex> \frac d {d + d_0 + 1} \cdot UNSAT(G) \le UNSAT(G') \le UNSAT(G)</tex>
 
* <tex> \frac d {d + d_0 + 1} \cdot UNSAT(G) \le UNSAT(G') \le UNSAT(G)</tex>
|proof=TODO
+
|proof=см. [http://eccc.hpi-web.de/report/2005/046 The PCP Theorem by Gap Amplification, Irit Dinur, 2005]
 
}}
 
}}
  
Строка 192: Строка 193:
 
|about=Усиление
 
|about=Усиление
 
|statement= Пусть <tex>\lambda < d</tex> и <tex>|\Sigma|</tex> произвольные константы. Тогда существует константа <tex>\beta_2=\beta_2(\lambda,d,|\Sigma|)>0</rex> такая, что для любого <tex>t \in \mathbb N</tex> и для любого <tex>d</tex>-регулярного графа условий <tex>G=\langle(V,E),\Sigma,\mathcal{C}\rangle</tex> с собственными циклами и <tex>\lambda(G)\le \lambda</tex>,<br/><tex>UNSAT(G^t) \ge \beta_2 \sqrt{t} \cdot min \left({UNSAT(G), \frac 1 t}\right)</tex>.
 
|statement= Пусть <tex>\lambda < d</tex> и <tex>|\Sigma|</tex> произвольные константы. Тогда существует константа <tex>\beta_2=\beta_2(\lambda,d,|\Sigma|)>0</rex> такая, что для любого <tex>t \in \mathbb N</tex> и для любого <tex>d</tex>-регулярного графа условий <tex>G=\langle(V,E),\Sigma,\mathcal{C}\rangle</tex> с собственными циклами и <tex>\lambda(G)\le \lambda</tex>,<br/><tex>UNSAT(G^t) \ge \beta_2 \sqrt{t} \cdot min \left({UNSAT(G), \frac 1 t}\right)</tex>.
|proof=TODO
+
|proof=см. [http://eccc.hpi-web.de/report/2005/046 The PCP Theorem by Gap Amplification, Irit Dinur, 2005]
 
}}
 
}}
  
 
Поскольку <tex>UNSAT(G) \le \frac 1 t</tex>, из жтой леммы следует что <tex>UNSAT(G^t) \ge O(\sqrt{t}) \cdot UNSAT(G)</tex>. Это основная техническая лемма.
 
Поскольку <tex>UNSAT(G) \le \frac 1 t</tex>, из жтой леммы следует что <tex>UNSAT(G^t) \ge O(\sqrt{t}) \cdot UNSAT(G)</tex>. Это основная техническая лемма.
 +
 
===Композиция===
 
===Композиция===
 
{{Определение
 
{{Определение
Строка 209: Строка 211:
 
|about=Композиция
 
|about=Композиция
 
|statement=Пусть существует тестер присвоений <tex>\mathcal{P}</tex> с константной вероятностью отклонения <tex>\epsilon > 0</tex> и алфавитом <tex>\Sigma_0</tex>, <tex>|\Sigma_0|=O(1)</tex>. Тогда существует <tex>\beta_3 > 0</tex>, зависящая только от <tex>\mathcal{P}</tex>, такая что любой граф условий <tex>G=\langle(V,E),\Sigma,\mathcal{C}\rangle</tex> может быть преобразован в <tex>G'=\langle(V',E'),\Sigma_0,\mathcal{C}'\rangle</tex>, обозначаемый <tex>G \circ \mathcal{C}</tex>, такой что <tex>size(G')=M(|\Sigma|) \cdot size(G)</tex> и <tex>\beta_3 \cdot UNSAT(G) \le UNSAT(G') \le UNSAT(G)</tex>
 
|statement=Пусть существует тестер присвоений <tex>\mathcal{P}</tex> с константной вероятностью отклонения <tex>\epsilon > 0</tex> и алфавитом <tex>\Sigma_0</tex>, <tex>|\Sigma_0|=O(1)</tex>. Тогда существует <tex>\beta_3 > 0</tex>, зависящая только от <tex>\mathcal{P}</tex>, такая что любой граф условий <tex>G=\langle(V,E),\Sigma,\mathcal{C}\rangle</tex> может быть преобразован в <tex>G'=\langle(V',E'),\Sigma_0,\mathcal{C}'\rangle</tex>, обозначаемый <tex>G \circ \mathcal{C}</tex>, такой что <tex>size(G')=M(|\Sigma|) \cdot size(G)</tex> и <tex>\beta_3 \cdot UNSAT(G) \le UNSAT(G') \le UNSAT(G)</tex>
|proof=
+
|proof=см. [http://eccc.hpi-web.de/report/2005/046 The PCP Theorem by Gap Amplification, Irit Dinur, 2005]
 
}}
 
}}
  
Строка 236: Строка 238:
 
|proof=Сведем удовлетворимость графа условий к нашей задаче. Пусть <tex>G</tex> задача удовлетворимости некоторого графа с <tex>|\Sigma|=3</tex>. Идей состоит в повторении применения основной теоремы до тех пор, пока число неудовлетворенности не станет постоянным.
 
|proof=Сведем удовлетворимость графа условий к нашей задаче. Пусть <tex>G</tex> задача удовлетворимости некоторого графа с <tex>|\Sigma|=3</tex>. Идей состоит в повторении применения основной теоремы до тех пор, пока число неудовлетворенности не станет постоянным.
  
Пусть <tex>G_0 = G</tex> и <tex>G_i(i \ge 1)</tex> &mdash; результат применения основной теоремы к <tex>G_{i-1}</tex>. Тогда для <tex>i \ge 1</tex> <tex>G</tex> &mdash; граф условий с алфавитом <tex>\Sigma_0</tex>. Пусть <tex>E_0</tex> &mdash; множество ребер <tex>G_0<tex> и <tex>k=log|E_0|=O(log n)</tex>.
+
Пусть <tex>G_0 = G</tex> и <tex>G_i(i \ge 1)</tex> &mdash; результат применения основной теоремы к <tex>G_{i-1}</tex>. Тогда для <tex>i \ge 1</tex> <tex>G</tex> &mdash; граф условий с алфавитом <tex>\Sigma_0</tex>. Пусть <tex>E_0</tex> &mdash; множество ребер <tex>G_0<tex> и <tex>k=\log|E_0|=O(\log n)</tex>.
  
Полнота показывается тривиально: если <tex>UNSAT(G_0)=0</tex>, то для всех <tex>i</tex> <tex>UNSAT(G_i)=0</tex>. Для обоснованности рассмотрим <tex>UNSAT(G_0) > 0</tex>. Если для некоторого <tex>i*<k</tex>, <tex>UNSAT(G_{i*}) \ge \frac \alpha 2</tex>, то из основной теоремы следует, что для всех <tex>i>i*</tex> <tex>UNSAT(G_i)\ge \alpha</tex>. На остальные <tex>i</tex> это распространяется по индукции <tex>UNSAT(G_i) \ge min(2^i UNSAT(G_0), \alpha).
+
Полнота показывается тривиально: если <tex>UNSAT(G_0)=0</tex>, то для всех <tex>i</tex> <tex>UNSAT(G_i)=0</tex>. Для обоснованности рассмотрим <tex>UNSAT(G_0) > 0</tex>. Если для некоторого <tex>i*<k</tex>, <tex>UNSAT(G_{i*}) \ge \frac \alpha 2</tex>, то из основной теоремы следует, что для всех <tex>i>i*</tex> <tex>UNSAT(G_i)\ge \alpha</tex>. На остальные <tex>i</tex> это распространяется по индукции <tex>UNSAT(G_i) \ge min(2^i UNSAT(G_0), \alpha)</tex>.
  
 
Если <tex>UNSAT(G_0)>0</tex>, то <tex>UNSAT(G_0)\ge \frac 1 {|E_0|}</tex>. Конечно, <tex>2^k UNSAT(G_0) > \alpha</tex>. Таким образом <tex>UNSAT(G_k) \ge \alpha</tex>.
 
Если <tex>UNSAT(G_0)>0</tex>, то <tex>UNSAT(G_0)\ge \frac 1 {|E_0|}</tex>. Конечно, <tex>2^k UNSAT(G_0) > \alpha</tex>. Таким образом <tex>UNSAT(G_k) \ge \alpha</tex>.
  
Мы доказали, что <tex>GAP</tex> <tex>\mathrm{NP}</tex>-трудная. В частности, для <tex>GAP-3SAT</tex>, надо преобразовать каждое условие к константное число дизъюнктов <tex>3CNF</tex>.
+
Такми образом <tex>\rho -GAP2CSP</tex> <tex>\mathrm{NP}</tex>-трудная. Достичь обоснованности <tex>\frac 1 2</tex> можно последовательным повторением <tex>u=\frac 1 {\log(\frac 1 {1 - \alpha})} </tex> раз. Тоесть создать новые условия, представляющие собой <tex>AND</tex> всех возможных <tex>u</tex>-наборов прежних условий. Конечно, при этом количество запросов на условие увеличится до <tex>2u</tex>.
  
 
}}
 
}}
 +
 
==Дополнительные материалы==
 
==Дополнительные материалы==
 
* [http://www.math.ias.edu/boaz/ExpanderCourse/|N. Linial and A. Wigderson. Expander graphs and their applications. Lecture notes of a course, 2003].
 
* [http://www.math.ias.edu/boaz/ExpanderCourse/|N. Linial and A. Wigderson. Expander graphs and their applications. Lecture notes of a course, 2003].
Строка 251: Строка 254:
 
* Irit Dinur and Omer Reingold. Assignment testers: Towards combinatorial proofs of the PCP theorem. In Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS), 2004.
 
* Irit Dinur and Omer Reingold. Assignment testers: Towards combinatorial proofs of the PCP theorem. In Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS), 2004.
 
==Источники==
 
==Источники==
* [http://eccc.hpi-web.de/report/2005/046/|The PCP Theorem by Gap Amplification, Irit Dinur, 2005].
+
* [http://eccc.hpi-web.de/report/2005/046 The PCP Theorem by Gap Amplification, Irit Dinur, 2005].
* [http://www.cs.utah.edu/~alfeld/LecturePDFs/pcp.pdf|The PCP Theorem, Notes by Scott Alfeld, 2008].
+
* [http://www.cs.utah.edu/~alfeld/LecturePDFs/pcp.pdf The PCP Theorem, Notes by Scott Alfeld, 2008].

Текущая версия на 05:14, 19 января 2019

Теорема ([math]\mathrm{PCP}[/math] теорема):
[math]\mathrm{PCP}[\log n, O(1)] = \mathrm{NP}[/math]

Классическое доказательство [math]\mathrm{PCP}[/math] теоремы громоздкое и довольно сложное для восприятия, рассмотрим вариант докаательства, предложенный Динур. Оно основано на том, что [math]\mathrm{PCP}[/math]-теорема эквивалентна [math]\mathrm{NP}[/math]-трудности задачи [math]\rho-GAPqCSP[/math].

Определения и леммы, используемые в доказательстве[править]

Определение:
[math]\mathcal{C}=\lbrace c_1,..., c_n\rbrace[/math] назовем множеством условий над множеством переменных [math]V[/math].


Определение:
Число неудовлетворенности [math]UNSAT(\mathcal{C})[/math] — минимальное подмножество неудовлетворенных условий для любых возможных назначений [math]V[/math]. [math]\mathcal{C}[/math] удовлетворимо тогда и только тогда, когда [math]UNSAT(\mathcal{C})=0[/math]. Если же [math]\mathcal{C}[/math] неудовлетворимо, тогда [math]UNSAT(\mathcal{C}) \ge \frac 1 n[/math].


Графы условий[править]

Нам понадобятся графы ограничений для двух переменных, которые определяются следующим образом:

Определение:
[math]G=\left\langle(V,E,\Sigma,\mathcal{C}\right\rangle[/math] называется графом условий, если:
  • [math](V,E)[/math] — неориентированный граф, называемый графом, лежащим в основе [math]G[/math].
  • Множество [math]V[/math] также представляется в виде множества переменных принимающих значениями из алфавита [math]\Sigma[/math]
  • Каждое ребро [math]e \in E[/math] содержит условие [math]c(e) \subseteq \Sigma^2[/math] и [math]\mathcal{C}=\lbrace c(e)\rbrace_{e \in E}[/math]. Условие [math]c(e)[/math] называется удовлетворенным парой [math](a, b)[/math], если [math](a, b) \in c(e)[/math]


Присваивание это отображение [math]\sigma:V \rightarrow \Sigma[/math], которое назначает каждой вершине из [math]V[/math] значение из [math]\Sigma[/math]. Для любого присвоения [math]\sigma[/math] определим [math]UNSAT_\sigma(G) = \operatorname*{Pr}\limits_{(u,v)\in E} [(\sigma(u),\sigma(v)) \notin c(e)][/math] и [math]UNSAT(G) = \operatorname*{min}\limits_\sigma UNSAT_\sigma(G)[/math].

Назовем [math]UNSAT(G)[/math] числом неудовлетворенности графа [math]G[/math]. Размером графа будем считать размер его описания [math]size(G)=O(|V|+|E| \cdot |\Sigma|^2)[/math]

Лемма:
Для заданного графа условий [math]G=\left\langle(V,E,\Sigma,\mathcal{C}\right\rangle[/math], где [math]|\Sigma|=3[/math] проверка утверждения [math]UNSAT(G)=0[/math][math]\mathrm{NP}[/math]-трудная задача.
Доказательство:
[math]\triangleright[/math]
Сведем [math]3Color[/math] к нашей задаче. Дан граф [math]G[/math], алфавит [math]\Sigma=\lbrace 1,2,3 \rbrace[/math] для трех цветов. Оснастим ребра условиями неравенства. Очевидно, что [math]G \in 3Color[/math] тогда и только тогда, когда [math]UNSAT(G)=0\lt tex\gt (Иногда удобно использовать одно и то же обозначение \lt tex\gt G[/math] для графа условий и графа, лежащего в его основе).
[math]\triangleleft[/math]

Экспандер графы[править]

Экспандер графы играют важную роль во многих теоретических результатах.


Определение:
[math]G=(V,E)[/math] [math]d[/math]-регулярный граф. Положим [math]E(S,\overline{S})=|(S \times \overline{S}) \cap E|[/math] равным количеству ребер их подмножества [math]S\in V[/math] в его дополнение. Определим реберное расширение как [math]h(G)=\operatorname*{min}\limits_{S:|S|\lt \frac {|V|} 2} \frac {E(S, \overline S)} {|S|}[/math]


Лемма (О экспандерах):
Существует [math]d_0 \in \mathbb{N}[/math] и [math]h_0 \gt 0[/math] такие, что есть построимое за полиномиальное время семейство [math]\lbrace X_n\rbrace_{n \in \mathbb{N}}[/math] [math]d_0[/math]-регулярных графов [math]X_n[/math] с [math]n[/math] вершинами таких, что [math]h(X_n) \ge h_0[/math].
Доказательство:
[math]\triangleright[/math]
см. The PCP Theorem by Gap Amplification, Irit Dinur, 2005
[math]\triangleleft[/math]
Лемма:
Пусть [math]G[/math] [math]d[/math]-регулярный граф, а [math]h(G)[/math] его реберное расширение. Тогда [math]\lambda(G) \le d - \frac {h(G)^2} d[/math]


Определение:
Собственным числом графа [math]\lambda[/math] называют собственное число его матрицы смежности.


Лемма:
Пусть [math]G[/math] [math]d[/math]-регулярный граф со вторым по величине собственным числом [math]\lambda[/math]. Пусть [math]F \subseteq E[/math] множество ребер. Вероятность [math]p[/math] того, что случайный путь, начинающийся со случайного ребра из [math]F[/math] на [math]i+1[/math] шаге попадет [math]F[/math] ограничена [math]\frac {|F|} {|E|} + \left({\frac {|\lambda|} d}\right)^i[/math].
Доказательство:
[math]\triangleright[/math]
см. The PCP Theorem by Gap Amplification, Irit Dinur, 2005
[math]\triangleleft[/math]

Операции на графах условий[править]

Для доказательства [math]\mathrm{PCP}[/math] теоремы потребуются три операции над графами уловий:

  • Препроцессинг. Простая операция, сохраняющая чило неудовлетворенности(примерно) и размер алфавита, но делающая граф лучше.
  • Усиление. Эта операция увеоичивает чило неудовлетворенности за счет увеличения размера алфавита.
  • Композицияю Эта операция уменьшает размер алфавита, сохраняя число неудовлетворенности(приблизительно).

Препроцессинг[править]

Под хорошим графом будем понимать регулярный, фиксированной степени экспандер граф.

Лемма (Препроцессинг):
существуют константы [math]0 \lt \lambda \lt d[/math] и [math]\beta_1 \gt 0[/math] такие, что любой граф условий [math]G[/math] может быть преобразован в граф условий [math]G'=prep(G)[/math] такой, что:
  • [math]G'[/math] [math]d[/math]-регулярный
  • [math]G'[/math] имеет тот же алфавит, что и [math]G[/math] и [math]size(G') = O(size(G))[/math].
  • [math]\beta_1 \cdot UNSAT(G) \le UNSAT(G') \le UNSAT(G)[/math]

Заметим, что третий пункт теммы гарантирует поддержание полноты, т.е. если [math]UNSAT(G)=0[/math], то и [math]UNSAT(G')=0[/math]. Доказательство этой леммы состоит из двух следующих лемм ([math]\beta_1=c \cdot \frac d {d + d_0 + 1}[/math]).

Лемма (Константная степень):
Любой граф условий [math]G = \langle (V,E),\Sigma,\mathcal{C}\rangle[/math] может быть преобразован в [math](d_0 + 1)[/math]-регулярный граф условий [math]G'=\langle (V',E'),\Sigma,\mathcal{C}'\rangle[/math] такой, что [math]|V'|[/math]=2
Доказательство:
[math]\triangleright[/math]
см. The PCP Theorem by Gap Amplification, Irit Dinur, 2005
[math]\triangleleft[/math]

Эта лемма известна как экспандер-замена(expander-replacement transformation).

Лемма (О расширении):
Пусть [math]d_0, h_0 \gt 0[/math] некоторые константы. Любой [math]d[/math]-регулярный граф условий [math]G[/math] может быть преобразован в [math]G'[/math] такой, что:
  • [math]G'[/math] [math](d + d_0 + 1)[/math]-регулярный, имеет собственные циклы и [math]\lambda(G') \le d + d_0 + 1 - \frac {h_0^2} {d + d_0 + 1} \lt deg(G')[/math]
  • [math]size(G')=O(size(G))[/math]
  • [math] \frac d {d + d_0 + 1} \cdot UNSAT(G) \le UNSAT(G') \le UNSAT(G)[/math]
Доказательство:
[math]\triangleright[/math]
см. The PCP Theorem by Gap Amplification, Irit Dinur, 2005
[math]\triangleleft[/math]

Усиление[править]

Это новая операция на системах условий, которая увеличивает число неудовлетворенности. Пусть [math]G=\langle (V,E),\Sigma,\mathcal{C}\rangle\lt tex\gt граф условий, \lt tex\gt t \in \mathbb{N}[/math]. Определим [math]G^t=\langle (V,\mathbf{E}),\Sigma^{d^{\lceil t/2\rceil}}, \mathcal{C}^t \rangle[/math] как следующий граф условий:

  • Веришины [math]G^t[/math] совпадают с вершинами [math]G[/math]
  • Ребра: [math]u[/math] и [math]v[/math] соединены [math]k[/math] ребрами в [math]\mathbf{E}[/math], если количество путей длины [math]t[/math] из [math]u[/math] в [math]v[/math] в графе [math]G[/math] равно [math]k[/math]
  • Алфавит: алфавит графа [math]G^t[/math] [math]\Sigma^{d^{\lceil t/2\rceil}}[/math], где каждой вершине сопоставлены значения ее соседей, достижимых за [math]\frac t 2[/math] шагов.
  • Условия: Условия сопоставленные ребру [math]e=(u,v) \in \mathbf{E}[/math] удовлетворены, если назначения для [math]u[/math] и [math]v[/math] согласованы с назначениями, удовлетворяющими условия, порожденные [math]\frac t 2[/math] соседями [math]u[/math] и [math]v[/math].

Если [math]UNSAT(G)=0[/math] тогда очевидно [math]UNSAT(G^t)=0[/math]. Интереснее доказательство того, что [math]UNSAT(G^t) \ge O(\sqrt{t} \cdot UNSAT(G)[/math].

Лемма (Усиление):
Пусть [math]\lambda \lt d[/math] и [math]|\Sigma|[/math] произвольные константы. Тогда существует константа [math]\beta_2=\beta_2(\lambda,d,|\Sigma|)\gt 0\lt /rex\gt такая, что для любого \lt tex\gt t \in \mathbb N[/math] и для любого [math]d[/math]-регулярного графа условий [math]G=\langle(V,E),\Sigma,\mathcal{C}\rangle[/math] с собственными циклами и [math]\lambda(G)\le \lambda[/math],
[math]UNSAT(G^t) \ge \beta_2 \sqrt{t} \cdot min \left({UNSAT(G), \frac 1 t}\right)[/math].
Доказательство:
[math]\triangleright[/math]
см. The PCP Theorem by Gap Amplification, Irit Dinur, 2005
[math]\triangleleft[/math]

Поскольку [math]UNSAT(G) \le \frac 1 t[/math], из жтой леммы следует что [math]UNSAT(G^t) \ge O(\sqrt{t}) \cdot UNSAT(G)[/math]. Это основная техническая лемма.

Композиция[править]

Определение:
Тестер присвоений с алфавитом [math]\Sigma_0[/math] и вероятностью отклонения [math]\epsilon \gt 0[/math] это полиномиальное преобразование [math]\mathcal{P}[/math], принимающее на вход схему [math]\Phi[/math] над будевыми переменными [math]X[/math] и дающую на выходе граф условий [math]G=\langle(V,E),\Sigma_0,\mathcal{C}\rangle[/math] такой, что [math]V \subset X[/math](в условном графе [math]V[/math] играет одновременно две роли: переменных и вершин. [math]Y \subset X[/math] подразумевает, что некоторые вершины из [math]V[/math] определены с помощью переменных [math]X[/math]). Пусть [math]V'=V \setminus X[/math] и [math]a : X \rightarrow \lbrace 0,1 \rbrace[/math] — присваивание.
  • (Полнота) Если [math]a \in SAT(\Phi)[/math] то существует [math]b : V' \rightarrow \Sigma_0[/math] такое, что [math]UNSAT_{a\cup{b}}(G)=0[/math]
  • (Обоснованность) Если [math]a \notin SAT(\Phi)[/math] то для всех [math]b : V' \rightarrow \Sigma_0[/math], [math]UNSAT_{a\cup{b}}(G) \ge \epsilon \cdot dist(a, SAT(\Phi))[/math].


Следует заметить, что не накладывается никаких ограничений ни на время работы [math]\mathcal{P}[/math] ни на [math]size(G)[/math]. Мы игнорируем размер схемы [math]\Phi[/math], которая может быть экспоненциальна относительно [math]|X|[/math].

Лемма (Композиция):
Пусть существует тестер присвоений [math]\mathcal{P}[/math] с константной вероятностью отклонения [math]\epsilon \gt 0[/math] и алфавитом [math]\Sigma_0[/math], [math]|\Sigma_0|=O(1)[/math]. Тогда существует [math]\beta_3 \gt 0[/math], зависящая только от [math]\mathcal{P}[/math], такая что любой граф условий [math]G=\langle(V,E),\Sigma,\mathcal{C}\rangle[/math] может быть преобразован в [math]G'=\langle(V',E'),\Sigma_0,\mathcal{C}'\rangle[/math], обозначаемый [math]G \circ \mathcal{C}[/math], такой что [math]size(G')=M(|\Sigma|) \cdot size(G)[/math] и [math]\beta_3 \cdot UNSAT(G) \le UNSAT(G') \le UNSAT(G)[/math]
Доказательство:
[math]\triangleright[/math]
см. The PCP Theorem by Gap Amplification, Irit Dinur, 2005
[math]\triangleleft[/math]

Основная теорема[править]

Основываясь на операциях с графами условий мы можем доказать основную теорему.

Теорема (Основная теорема):
Для любого [math]\Sigma[/math], [math]|\Sigma|=O(1)[/math] существуют константы [math]C \gt 0[/math] и [math]0 \lt \alpha \lt 1[/math] такие, что для данного графа условий [math]G=\langle(V,E),\Sigma,\mathcal{C}\rangle[/math] за полиномиальное время можно построить граф условий [math]G'=\langle(V',E'),\Sigma_0,\mathcal{C}'\rangle[/math] такой, что:
  • [math]size(G') \le C \cdot size(G)[/math] и [math]|\Sigma_0| = O(1)[/math]
  • (Полнота) Если [math]UNSAT(G)=0[/math], то [math]UNSAT(G')=0[/math]
  • (Обоснованность) [math]UNSAT(G') \ge min(2 \cdot UNSAT(G), \alpha)[/math]
Доказательство:
[math]\triangleright[/math]

Построим [math]G'[/math] по [math]G[/math] следующим образом: [math]G'=(prep(G))^t \circ \mathcal{P}[/math].

  1. (Препроцессинг) Пусть [math]H_1=prep(G)[/math]. Существуют некоторые глобальные константы [math]\lambda \lt d [/math] и [math]\beta_1 \gt 0[/math] такие, что [math]H_1[/math] [math]d[/math]-регулярный, имеет тот же алфавит, что и [math]G[/math], [math]\lambda(H_1) \le \lambda \lt d[/math] и [math]\beta_1 \cdot UNSAT*G( \le UNSAT(H_1) \le UNSAT(G)[/math].
  2. (Усиление) Пусть [math]H_2=(H_1)^t[/math] для достаточно большой константы [math] t \gt 1[/math], которую определим ниже. Существует некоторая константа [math]\beta_2=\beta(\lambda, d, |\Sigma|) \gt 0[/math], для которой [math]UNSAT(H_2) \ge \beta_2 \sqrt{t} \cdot min(UNSAT(H_1), \frac 1 t)[/math]. Однако, алфавит вырос до [math]\Sigma^{d^{\lceil t / 2 \rceil}}[/math].
  3. (Композиция) Пусть [math]G'=H_2 \circ \mathcal{P}[/math]. Это уменьшит алфавит до [math]\Sigma_0[/math], при [math]\beta_3 \cdot UNSAT(H_2) \le UNSAT(G') \le UNSAT(H_2)[/math] для некоторой [math]\beta_3 \gt 0 [/math].

Проверим выполнение условий теоремы. Размер [math]G'[/math] линеен относительно размера[math]G[/math], поскольку на каждом шагу увеличивался линейно. Полнота явно поддерживается на каждом шаге. Теперь выберем [math]t=\left\lceil\left({\frac 2 {\beta_1\beta_2\beta_3}}\right)^2\right\rceil[/math]. Пусть [math]\alpha=\frac {\beta_3\beta_2} {sqrt{t}}[/math]. Таким образом,

[math]UNSAT(G') \ge \beta_3 \cdot UNSAT(H_2)[/math]
[math]\ge \beta_3 \cdot \beta_2 \sqrt{t} \cdot min(UNSAT(H_1), \frac 1 t)[/math]
[math]\ge \beta_3 \cdot \beta_2 \sqrt{t} \cdot min(\beta_1 UNSAT(G_, \frac 1 t) [/math]
[math]\ge min(2 \cdot UNSAT(G), \alpha)[/math]
[math]\triangleleft[/math]

Доказательство PCP теоремы[править]

Лемма:
Следствием из основной теоремы является [math]\mathrm{NP}[/math]-трудность [math]GAP-3SAT_s[/math].
Доказательство:
[math]\triangleright[/math]

Сведем удовлетворимость графа условий к нашей задаче. Пусть [math]G[/math] задача удовлетворимости некоторого графа с [math]|\Sigma|=3[/math]. Идей состоит в повторении применения основной теоремы до тех пор, пока число неудовлетворенности не станет постоянным.

Пусть [math]G_0 = G[/math] и [math]G_i(i \ge 1)[/math] — результат применения основной теоремы к [math]G_{i-1}[/math]. Тогда для [math]i \ge 1[/math] [math]G[/math] — граф условий с алфавитом [math]\Sigma_0[/math]. Пусть [math]E_0[/math] — множество ребер [math]G_0\lt tex\gt и \lt tex\gt k=\log|E_0|=O(\log n)[/math].

Полнота показывается тривиально: если [math]UNSAT(G_0)=0[/math], то для всех [math]i[/math] [math]UNSAT(G_i)=0[/math]. Для обоснованности рассмотрим [math]UNSAT(G_0) \gt 0[/math]. Если для некоторого [math]i*\lt k[/math], [math]UNSAT(G_{i*}) \ge \frac \alpha 2[/math], то из основной теоремы следует, что для всех [math]i\gt i*[/math] [math]UNSAT(G_i)\ge \alpha[/math]. На остальные [math]i[/math] это распространяется по индукции [math]UNSAT(G_i) \ge min(2^i UNSAT(G_0), \alpha)[/math].

Если [math]UNSAT(G_0)\gt 0[/math], то [math]UNSAT(G_0)\ge \frac 1 {|E_0|}[/math]. Конечно, [math]2^k UNSAT(G_0) \gt \alpha[/math]. Таким образом [math]UNSAT(G_k) \ge \alpha[/math].

Такми образом [math]\rho -GAP2CSP[/math] [math]\mathrm{NP}[/math]-трудная. Достичь обоснованности [math]\frac 1 2[/math] можно последовательным повторением [math]u=\frac 1 {\log(\frac 1 {1 - \alpha})} [/math] раз. Тоесть создать новые условия, представляющие собой [math]AND[/math] всех возможных [math]u[/math]-наборов прежних условий. Конечно, при этом количество запросов на условие увеличится до [math]2u[/math].
[math]\triangleleft[/math]

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

  • Linial and A. Wigderson. Expander graphs and their applications. Lecture notes of a course, 2003.
  • Michael Sipser and Daniel A. Spielman. Expander codes. IEEE Trans. Inform. Theory, 42(6, part 1):1710–1722, 1996. Codes and complexity.
  • C. Papadimitriou and M. Yannakakis. Optimization, approximation and complexity classes. Journal of Computer and System Sciences, 3:425–440, 1991.
  • Irit Dinur and Omer Reingold. Assignment testers: Towards combinatorial proofs of the PCP theorem. In Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS), 2004.

Источники[править]