Изменения

|definition=<tex>qCSP</tex> представляет собой <tex>\varphi</tex> &mdash; набор функций <tex>\varphi_1, \ldots, \varphi_m</tex> из <tex>\{0, 1\}^n</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>u \in \{0, 1\}^n</tex> удовлетворяет <tex>\varphi_i</tex>, если <tex>\varphi_i(u) = 1</tex>.

 ==<tex>\rho</tex>ρ-GAPqCSP==

|id=pcp_th|about=<tex>\mathrm{PCP}</tex> теорема|statement=<tex>\mathrm{PCP}[\log n, O(1)] = \mathrm{NP}</tex>}} {{Теорема|statement=Существуют <tex>q \in \mathbb{N}, \rho \in (0, 1)</tex> такие, что задача <tex>\rho-GAPqCSP</tex>-GAP qCSP &mdash; <tex>\mathrm{NP}</tex>-трудная.

{{УтверждениеЛемма|statement=Теорема выше эквивалентна теореме о том, что Из <tex>\mathrm{NPPCP}</tex> = -теоремы следует <tex>\mathrm{PCPNP}_{\frac 1 2 ,1}(</tex>-трудность задачи <tex>\log(n), 1)rho-GAPqCSP</tex>.

Покажем, что <tex>\frac 1) Пусть 2 -GAPqCSP</tex> <tex>\mathrm{NP }</tex>-трудная для некоторой константы <tex>q</tex>. Для этого достаточно свести <tex>\subseteqmathrm{NP}</tex>-полную задачу, например <tex>3SAT</tex> к <tex>\frac 1 2 -GAPqCSP</tex> для некоторой константы <tex>q</tex>. Из <tex>\mathrm{PCP}</tex>-теоремы следует, что для <tex>3SAT</tex> существует <tex>\mathrm{PCP(1}</tex>-система, в которой верифаер <tex>V</tex> делает константное число запросов <tex>q</tex> и использует <tex>c \log(n)</tex>)монет для некоторйо константы <tex>c</tex>. Для входа <tex>x</tex> и монет <tex>r</tex> определим <tex>V_{x,r}</tex> как функцию, принимающую на вход доказательство <tex>\pi</tex> и возвращающую <tex>1</tex>, если верифаер <tex>V</tex> принимает доказательство <tex>\pi</tex> на входе <tex>x</tex> с монетами <tex>r</tex>. ДокажемЗаметим, что задача 3SAT сводится к <tex>V_{x,r}</tex> зависит не больше, чем от <tex>q</tex> позиций. Таким образом для любого <tex>x \fracin {0,1}^n</tex> набор <tex>\phi=\lbrace V_{x,r}\rbrace_{2r \in \lbrace 0,1\rbrace^{c\log n}}</tex>-GAP &mdash; экземпляр <tex>qCSP</tex> полиномиального размера. Так как <tex>V</tex> работает за полиномиальное время, апреобразование <tex>x</tex> в <tex>\phi</tex> также работает за полиномиальное время. Теперь полнота и обоснованность: если <tex>x \in 3SAT</tex>, значитто <tex>\phi</tex> удовлетворяет <tex>val(\phi)=1</tex>, а если <tex>x \notin 3SAT</tex> то <tex>\rhophi</tex> удовлетворяет <tex>val(\phi) \le \frac 1 2</tex>-GAP qCSP является NP-сложной.}}

По нашему предположению {{Лемма|statement= Из <tex>\mathrm{NP}</tex>-трудности задачи <tex>\rho-GAPqCSP</tex> следует <tex>\mathrm{PCP}</tex>-теорема.|proof=Исходя из <tex>\mathrm{NP}</tex>-трудности задачи <tex>\rho-GAPqCSP</tex> для задачи некоторых констант <tex>q, \rho < 1</tex> легко построить <tex>\mathrm{PCP}</tex> систему с <tex>q</tex> запросами к доказательству, обоснованностью <tex>3SAT\rho</tex> существует и использующую логарифмическое число случайных бит. Сначала верифаер <tex>V</tex> с доказательством запускает сведение <tex>f(x)</tex>, чтобы получить экземпляр задачи <tex>qCSP</tex> <tex>\phi=\lbrace\phi_i\rbrace_{i=1}^{m}</tex>. Будем считать, что доказательство <tex>\pi</tex> это назначение переменных <tex>\phi</tex>. Проверять будем случайно выбирая <tex>i \in [1,m]</tex> и обращается он к нему проверяя, удовлетворяется ли <tex>\phi_i</tex> (для этого требуется <tex>q</tex> раззапросов). Действительно, если <tex>x \in L</tex>, верифаер примет его с вероятностью <tex>1</tex>. Если же <tex>x \notin L</tex>, а случайной лентой пользуется верифаер примет его с вероятностью не больше <tex>c \log(n)rho</tex>. Обоснованность может быть увеличена до <tex>\frac 1 2</tex> за счет увеличения количества завпросов к доказательству и использованных случайных бит в константное количество раз.}}

Теперь для любого входа <tex>x \in \{0Стоит заметить, 1\}^nчто </tex> и случайной ленты <tex>r \in \mathrm{0, 1\}^{clog(n)PCP}</tex> определим функцию <tex>V_{x, r}</tex> такую, что для доказательства -теорема эквивалентна также <tex>\pi</tex> возвращает 1, если верифаер принимает доказательство <tex>\pi</tex>, имея на входе <tex>x</tex> и ленту <tex>r</tex>. Получается что набор <tex>\varphi={V_mathrm{x, r}NP}</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}rho-GAP3SAT</tex>.

2) Пусть <tex>\rho</tex>-GAP qCSP &mdash; NP-трудная. Переведём её в задачу PCP c q запросами к доказательству и с вероятностью <tex>\rho</tex>. Нам дают на вход <tex>x</tex>, верифаер преобразовывает вход в qCSP задачу. В доказательстве <tex>\pi</tex> будут храниться значения переменных набора <tex>\varphi = \{\varphi_i\}_{i = 1}^{m}<Источники==* [http://tex>www. Теперь мы случайно выбираем <tex>i \in [1cs.princeton.m]<edu/theory/tex> и проверяем <tex>\varphi_i<complexity/tex> на наборе из доказательства, сделав выборку из q элементовpcpchap.pdf S. Если <tex>x \in L</tex>Arora, то верифаер принимает с вероятностью 1, иначе принимает с вероятностью <tex>\rho</tex>B. Мы можем из <tex>\rho</tex> сделать <tex>\frac{1}{2}</tex>Barak.}}Computational Complexity: A Modern Approach, 2007]