143
правки
Изменения
немного косметических правок.
Классической доказательство <tex>\mathrm{PCP}</tex>-теоремы довольно громоздкое и трудное для понимания, однако несложно показать эквивалентность <tex>\mathrm{PCP}</tex>-теоремы <tex>\mathrm{NP}</tex>-трудности задачи аппроксимации.
==Задача qCSP==
{{Определение
|definition=<tex>qCSP</tex> представляет собой <tex>\varphi</tex> — набор функций <tex>\varphi_1, \ldots, \varphi_m</tex> из <tex>\{0, 1\}^2n</tex> в <tex>\{0, 1\}</tex>, такие что <tex>\varphi_i</tex> зависит только не больше, сем от <tex>q</tex> заданных параметров. То есть для <tex>\forall i \in [1..m]</tex> существуют <tex>j_1, \ldots, j_q \in [1..n]</tex> и функция <tex>f:\{0, 1\}^q \rightarrow \{0, 1\}</tex>, такие что <tex>\varphi_i(u) = f(u_{j_1}, \ldots, u_{j_q})</tex> для любого <tex>u \in \{0, 1\}^n</tex>.
<tex>val(\varphi) = \frac{\sum_{i = 1}^{m} \varphi_i(u)}{m}.</tex> Если <tex>val(\varphi) = 1</tex>, то <tex>\varphi</tex> - удовлетворима.
}}
==<tex>\rho</tex>-GAPqCSP==
{{Определение
|definition=<tex>\rho \in (0, 1)</tex>. Задача <tex>\rho</tex>-GAP qCSP - определить для формулы qCSP — <tex>\varphi</tex>:
<tex>\bullet</tex> <tex>val(\varphi) \leq \rho</tex>, то "NO".
}}
==Эквивалентность PCP-теоремы и NP-трудности задачи об аппроксимации==
{{Теорема
|statement=Существуют <tex>q \in \mathbb{N}, \rho \in (0, 1)</tex> такие, что задача <tex>\rho</tex>-GAP qCSP — <tex>\mathrm{NP}</tex>-трудная.
}}
{{Утверждение
|statement=Теорема выше эквивалентна теореме о том, что <tex>\mathrm{NP }</tex> = <tex>\mathrm{PCP(}_{\frac 12 , <tex>1}(\log(n), 1)</tex>).
|proof=
1) Пусть NP <tex>\subseteq</tex> PCP(1, <tex>log(n)</tex>). Докажем, что задача 3SAT сводится к <tex>\frac{1}{2}</tex>-GAP qCSP, а, значит, <tex>\rho</tex>-GAP qCSP является NP-сложной.
По нашему предположению для задачи <tex>3SAT </tex> существует верифаер <tex>V</tex> с доказательством <tex>\pi</tex> и обращается он к нему <tex>q</tex> раз, а случайной лентой пользуется <tex>clogc \log(n)</tex> раз.
Теперь для любого входа <tex>x \in \{0, 1\}^n</tex> и случайной ленты <tex>r \in \{0, 1\}^{clog(n)}</tex> определим функцию <tex>V_{x, r}</tex> такую, что для доказательства <tex>\pi</tex> возвращает 1, если верифаер принимает доказательство <tex>\pi</tex>, имея на входе <tex>x</tex> и ленту <tex>r</tex>. Получается что набор <tex>\varphi={V_{x, r}}</tex> для всех <tex>x</tex> и <tex>r</tex> является <tex>qCSP </tex> полиномиального размера. Так как верифаер работает за полиномиальное время, то <tex>x</tex> сводится к <tex>\varphi</tex> за полиномиальное время. И если <tex>x \in</tex> 3SAT, то <tex>val(\varphi) = 1</tex>, и <tex>x \not\in</tex> 3SAT, то <tex>val(\varphi) \leq \frac{1}{2}</tex>.
2) Пусть <tex>\rho</tex>-GAP qCSP — NP-трудная. Переведём её в задачу PCP c q запросами к доказательству и с вероятностью <tex>\rho</tex>. Нам дают на вход <tex>x</tex>, верифаер преобразовывает вход в qCSP задачу. В доказательстве <tex>\pi</tex> будут храниться значения переменных набора <tex>\varphi = \{\varphi_i\}_{i = 1}^{m}</tex>. Теперь мы случайно выбираем <tex>i \in [1..m]</tex> и проверяем <tex>\varphi_i</tex> на наборе из доказательства, сделав выборку из q элементов. Если <tex>x \in L</tex>, то верифаер принимает с вероятностью 1, иначе принимает с вероятностью <tex>\rho</tex>. Мы можем из <tex>\rho</tex> сделать <tex>\frac{1}{2}</tex>.
}}
