Эквивалентность PCP-теоремы и теоремы о трудности аппроксимации

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

Задача qCSP

Определение:

[math]qCSP[/math] представляет собой [math]\varphi[/math] — набор функций [math]\varphi_1, \ldots, \varphi_m[/math] из [math]\{0, 1\}^n[/math] в [math]\{0, 1\}[/math], такие что [math]\varphi_i[/math] зависит не больше, сем от [math]q[/math] заданных параметров. То есть для [math]\forall i \in [1..m][/math] существуют [math]j_1, \ldots, j_q \in [1..n][/math] и функция [math]f:\{0, 1\}^q \rightarrow \{0, 1\}[/math], такие что [math]\varphi_i(u) = f(u_{j_1}, \ldots, u_{j_q})[/math] для любого [math]u \in \{0, 1\}^n[/math]. Говорят, что набор [math]u \in \{0, 1\}^n[/math] удовлетворяет [math]\varphi_i[/math], если [math]\varphi_i(u) = 1[/math]. [math]val(\varphi) = \frac{\sum_{i = 1}^{m} \varphi_i(u)}{m}.[/math] Если [math]val(\varphi) = 1[/math], то [math]\varphi[/math] - удовлетворима.

[math]\rho[/math]-GAPqCSP

Определение:

[math]\rho \in (0, 1)[/math]. Задача [math]\rho[/math]-GAP qCSP - определить для формулы qCSP — [math]\varphi[/math]: [math]\bullet[/math] [math]\varphi[/math] удовлетворима, то "YES". [math]\bullet[/math] [math]val(\varphi) \leq \rho[/math], то "NO".

Эквивалентность PCP-теоремы и NP-трудности задачи об аппроксимации

Теорема:

Существуют [math]q \in \mathbb{N}, \rho \in (0, 1)[/math] такие, что задача [math]\rho[/math]-GAP qCSP — [math]\mathrm{NP}[/math]-трудная.

Утверждение:

Теорема выше эквивалентна теореме о том, что [math]\mathrm{NP}[/math] = [math]\mathrm{PCP}_{\frac 1 2 ,1}(\log(n), 1)[/math].

[math]\triangleright[/math]

1) Пусть NP [math]\subseteq[/math] PCP(1, [math]log(n)[/math]). Докажем, что задача 3SAT сводится к [math]\frac{1}{2}[/math]-GAP qCSP, а, значит, [math]\rho[/math]-GAP qCSP является NP-сложной. По нашему предположению для задачи [math]3SAT[/math] существует верифаер [math]V[/math] с доказательством [math]\pi[/math] и обращается он к нему [math]q[/math] раз, а случайной лентой пользуется [math]c \log(n)[/math] раз. Теперь для любого входа [math]x \in \{0, 1\}^n[/math] и случайной ленты [math]r \in \{0, 1\}^{clog(n)}[/math] определим функцию [math]V_{x, r}[/math] такую, что для доказательства [math]\pi[/math] возвращает 1, если верифаер принимает доказательство [math]\pi[/math], имея на входе [math]x[/math] и ленту [math]r[/math]. Получается что набор [math]\varphi={V_{x, r}}[/math] для всех [math]x[/math] и [math]r[/math] является [math]qCSP[/math] полиномиального размера. Так как верифаер работает за полиномиальное время, то [math]x[/math] сводится к [math]\varphi[/math] за полиномиальное время. И если [math]x \in[/math] 3SAT, то [math]val(\varphi) = 1[/math], и [math]x \not\in[/math] 3SAT, то [math]val(\varphi) \leq \frac{1}{2}[/math]. 2) Пусть [math]\rho[/math]-GAP qCSP — NP-трудная. Переведём её в задачу PCP c q запросами к доказательству и с вероятностью [math]\rho[/math]. Нам дают на вход [math]x[/math], верифаер преобразовывает вход в qCSP задачу. В доказательстве [math]\pi[/math] будут храниться значения переменных набора [math]\varphi = \{\varphi_i\}_{i = 1}^{m}[/math]. Теперь мы случайно выбираем [math]i \in [1..m][/math] и проверяем [math]\varphi_i[/math] на наборе из доказательства, сделав выборку из q элементов. Если [math]x \in L[/math], то верифаер принимает с вероятностью 1, иначе принимает с вероятностью [math]\rho[/math]. Мы можем из [math]\rho[/math] сделать [math]\frac{1}{2}[/math].

[math]\triangleleft[/math]