Эквивалентность 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] - удовлетворима.

ρ-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]\mathrm{PCP}[/math] теорема):

[math]\mathrm{PCP}[\log n, O(1)] = \mathrm{NP}[/math]

Теорема:

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

Лемма:

Из [math]\mathrm{PCP}[/math]-теоремы следует [math]\mathrm{NP}[/math]-трудность задачи [math]\rho-GAPqCSP[/math].

Доказательство:

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Лемма:

Из [math]\mathrm{NP}[/math]-трудности задачи [math]\rho-GAPqCSP[/math] следует [math]\mathrm{PCP}[/math]-теорема.

Доказательство:

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Стоит заметить, что [math]\mathrm{PCP}[/math]-теорема эквивалентна также [math]\mathrm{NP}[/math]-трудности задачи [math]\rho-GAP3SAT[/math].

Источники

• S.Arora,B.Barak. Computational Complexity: A Modern Approach, 2007