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

Материал из Викиконспекты
Перейти к: навигация, поиск
(не показаны 2 промежуточные версии 1 участника)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|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>\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\}^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>.
  
 
Назовём распределение <tex>u \in \{0, 1\}</tex> удовлетворяет <tex>\varphi_i</tex>, если <tex>\varphi_i(u) = 1</tex>.
 
Назовём распределение <tex>u \in \{0, 1\}</tex> удовлетворяет <tex>\varphi_i</tex>, если <tex>\varphi_i(u) = 1</tex>.
Строка 8: Строка 8:
  
 
{{Определение
 
{{Определение
|definition=<tex>\rho \in (0, 1)</tex>. Задача <tex>\rho</tex>-GAP qCSP - определить для формулы q-CSP &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".
Строка 24: Строка 24:
 
По нашему предположению для задачи 3SAT существует верифаер <tex>V</tex> с доказательством <tex>\pi</tex> и обращается он к нему <tex>q</tex> раз, а случайной лентой пользуется <tex>clog(n)</tex> раз.
 
По нашему предположению для задачи 3SAT существует верифаер <tex>V</tex> с доказательством <tex>\pi</tex> и обращается он к нему <tex>q</tex> раз, а случайной лентой пользуется <tex>clog(n)</tex> раз.
  
Теперь для любого входа <tex>x \in \{0, 1\}^n</tex> и <tex>r \in \{0, 1\}^{clog(n)}</tex> определим функцию <tex>V_{x, r}</tex> такую, что для доказательства &mdash; <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>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>.
 +
 
 +
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>.
 
}}
 
}}

Версия 00:47, 3 июня 2012

Определение:
[math]qCSP[/math] представляет собой [math]\varphi[/math] — набор функций [math]\varphi_1, \ldots, \varphi_m[/math] из [math]\{0, 1\}^2[/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\}[/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 \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".


Теорема:
Существуют [math]q \in \mathbb{N}, \rho \in (0, 1)[/math] такие, что задача [math]\rho[/math]-GAP qCSP — NP-трудная.
Утверждение:
Теорема выше эквивалентна теореме о том, что NP = PCP(1, [math]log(n)[/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-сложной.

По нашему предположению для задачи 3SAT существует верифаер [math]V[/math] с доказательством [math]\pi[/math] и обращается он к нему [math]q[/math] раз, а случайной лентой пользуется [math]clog(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] является qCSP полиномиального размера. Так как верифаер работает за полиномиальное время, то [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]