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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |definition=<tex>qCSP</tex> представляет собой <tex>\varphi</tex> — набор функций <tex>\varphi_1, \ldo...»)
 
(Эквивалентность PCP-теоремы и NP-трудности задачи об аппроксимации)
(не показано 9 промежуточных версий 2 участников)
Строка 1: Строка 1:
 +
Классическое доказательство <tex>\mathrm{PCP}</tex>-теоремы довольно громоздкое и трудное для понимания, однако несложно показать эквивалентность <tex>\mathrm{PCP}</tex>-теоремы <tex>\mathrm{NP}</tex>-трудности задачи аппроксимации.
 +
==Задача qCSP==
 
{{Определение
 
{{Определение
|definition=<tex>qCSP</tex> представляет собой <tex>\varphi</tex> &mdash; набор функций <tex>\varphi_1, \ldots, \varphi_m</tex> из <tex>\{0, 1\}^2</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>.
+
|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\}</tex> удовлетворяет <tex>\varphi_i</tex>, если <tex>\varphi_i(u) = 1</tex>.
+
Говорят, что назначение <tex>u \in \{0, 1\}^n</tex> удовлетворяет <tex>\varphi_i</tex>, если <tex>\varphi_i(u) = 1</tex>.
  
 
<tex>val(\varphi) = \frac{\sum_{i = 1}^{m} \varphi_i(u)}{m}.</tex> Если <tex>val(\varphi) = 1</tex>, то <tex>\varphi</tex> - удовлетворима.
 
<tex>val(\varphi) = \frac{\sum_{i = 1}^{m} \varphi_i(u)}{m}.</tex> Если <tex>val(\varphi) = 1</tex>, то <tex>\varphi</tex> - удовлетворима.
 
}}
 
}}
  
 +
==ρ-GAPqCSP==
 
{{Определение
 
{{Определение
 
|definition=<tex>\rho \in (0, 1)</tex>. Задача <tex>\rho</tex>-GAP qCSP - определить для формулы qCSP &mdash; <tex>\varphi</tex>:
 
|definition=<tex>\rho \in (0, 1)</tex>. Задача <tex>\rho</tex>-GAP qCSP - определить для формулы qCSP &mdash; <tex>\varphi</tex>:
 
<tex>\bullet</tex> <tex>\varphi</tex> удовлетворима, то "YES".
 
<tex>\bullet</tex> <tex>\varphi</tex> удовлетворима, то "YES".
 
<tex>\bullet</tex> <tex>val(\varphi) \leq \rho</tex>, то "NO".
 
<tex>\bullet</tex> <tex>val(\varphi) \leq \rho</tex>, то "NO".
 +
}}
 +
==Эквивалентность PCP-теоремы и NP-трудности задачи об аппроксимации==
 +
{{Теорема
 +
|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</tex>-GAP qCSP &mdash; NP-трудная.
+
|statement=Существуют <tex>q \in \mathbb{N}, \rho \in (0, 1)</tex> такие, что задача <tex>\rho-GAPqCSP</tex> &mdash; <tex>\mathrm{NP}</tex>-трудная.
 
}}
 
}}
  
{{Утверждение
+
{{Лемма
|statement=Теорема выше эквивалентна теореме о том, что NP = PCP(1, <tex>log(n)</tex>).
+
|statement= Из <tex>\mathrm{PCP}</tex>-теоремы следует <tex>\mathrm{NP}</tex>-трудность задачи <tex>\rho-GAPqCSP</tex>.
 
|proof=
 
|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>\frac 1 2 -GAPqCSP</tex> <tex>\mathrm{NP}</tex>-трудная для некоторой константы <tex>q</tex>. Для этого достаточно свести <tex>\mathrm{NP}</tex>-полную задачу, например <tex>3SAT</tex> к <tex>\frac 1 2 -GAPqCSP</tex> для некоторой константы <tex>q</tex>. Из <tex>\mathrm{PCP}</tex>-теоремы следует, что для <tex>3SAT</tex> существует <tex>\mathrm{PCP}</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>. Заметим, что <tex>V_{x,r}</tex> зависит не больше, чем от <tex>q</tex> позиций. Таким образом для любого <tex>x \in {0,1}^n</tex> набор <tex>\phi=\lbrace V_{x,r}\rbrace_{r \in \lbrace 0,1\rbrace^{c\log n}}</tex> &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>\phi</tex> удовлетворяет <tex>val(\phi) \le \frac 1 2</tex>.
 +
}}
  
По нашему предположению для задачи 3SAT существует верифаер <tex>V</tex> с доказательством <tex>\pi</tex> и обращается он к нему <tex>q</tex> раз, а случайной лентой пользуется <tex>clog(n)</tex> раз.
+
{{Лемма
 +
|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>\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>\rho</tex>.  Обоснованность может быть увеличена до <tex>\frac 1 2</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> является qCSP полиномиального размера. Так как верифаер работает за полиномиальное время, то <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>.
+
Стоит заметить, что <tex>\mathrm{PCP}</tex>-теорема эквивалентна также <tex>\mathrm{NP}</tex>-трудности задачи <tex>\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}</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>.
+
==Источники==
}}
+
* [http://www.cs.princeton.edu/theory/complexity/pcpchap.pdf S.Arora,B.Barak. Computational Complexity: A Modern Approach, 2007]

Версия 01:50, 25 мая 2018

Классическое доказательство [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].

Источники