Эквивалентность PCP-теоремы и теоремы о трудности аппроксимации — различия между версиями
Filchenko (обсуждение | вклад) (собственно PCP) |
м (rollbackEdits.php mass rollback) |
||
(не показано 5 промежуточных версий 3 участников) | |||
Строка 2: | Строка 2: | ||
==Задача qCSP== | ==Задача qCSP== | ||
{{Определение | {{Определение | ||
− | |definition=<tex>qCSP</tex> представляет собой <tex>\varphi</tex> — набор функций <tex>\varphi_1, \ldots, \varphi_m</tex> из <tex>\{0, 1\}^n</tex> в <tex>\{0, 1\}</tex>, такие что <tex>\varphi_i</tex> зависит не больше, | + | |definition=<tex>qCSP</tex> представляет собой <tex>\varphi</tex> — набор функций <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>u \in \{0, 1\}^n</tex> удовлетворяет <tex>\varphi_i</tex>, если <tex>\varphi_i(u) = 1</tex>. | ||
Строка 8: | Строка 8: | ||
<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== | ==ρ-GAPqCSP== | ||
{{Определение | {{Определение | ||
Строка 18: | Строка 19: | ||
|id=pcp_th | |id=pcp_th | ||
|about=<tex>\mathrm{PCP}</tex> теорема | |about=<tex>\mathrm{PCP}</tex> теорема | ||
− | |statement=<tex>\mathrm{PCP}[log | + | |statement=<tex>\mathrm{PCP}[\log n, O(1)] = \mathrm{NP}</tex> |
}} | }} | ||
Строка 28: | Строка 29: | ||
|statement= Из <tex>\mathrm{PCP}</tex>-теоремы следует <tex>\mathrm{NP}</tex>-трудность задачи <tex>\rho-GAPqCSP</tex>. | |statement= Из <tex>\mathrm{PCP}</tex>-теоремы следует <tex>\mathrm{NP}</tex>-трудность задачи <tex>\rho-GAPqCSP</tex>. | ||
|proof= | |proof= | ||
− | Покажем, что <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>\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> — экземпляр <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>. |
}} | }} | ||
Текущая версия на 19:29, 4 сентября 2022
Классическое доказательство
-теоремы довольно громоздкое и трудное для понимания, однако несложно показать эквивалентность -теоремы -трудности задачи аппроксимации.Задача qCSP
Определение: |
Говорят, что назначение удовлетворяет , если . Если , то - удовлетворима. | представляет собой — набор функций из в , такие что зависит не больше, чем от заданных параметров. То есть для существуют и функция , такие что для любого .
ρ-GAPqCSP
Определение: |
удовлетворима, то "YES". , то "NO". | . Задача -GAP qCSP - определить для формулы qCSP — :
Эквивалентность PCP-теоремы и NP-трудности задачи об аппроксимации
Теорема ( | теорема):
Теорема: |
Существуют такие, что задача — -трудная. |
Лемма: |
Из -теоремы следует -трудность задачи . |
Доказательство: |
Покажем, что | -трудная для некоторой константы . Для этого достаточно свести -полную задачу, например к для некоторой константы . Из -теоремы следует, что для существует -система, в которой верифаер делает константное число запросов и использует монет для некоторйо константы . Для входа и монет определим как функцию, принимающую на вход доказательство и возвращающую , если верифаер принимает доказательство на входе с монетами . Заметим, что зависит не больше, чем от позиций. Таким образом для любого набор — экземпляр полиномиального размера. Так как работает за полиномиальное время, преобразование в также работает за полиномиальное время. Теперь полнота и обоснованность: если , то удовлетворяет , а если то удовлетворяет .
Лемма: |
Из -трудности задачи следует -теорема. |
Доказательство: |
Исходя из | -трудности задачи для некоторых констант легко построить систему с запросами к доказательству, обоснованностью и использующую логарифмическое число случайных бит. Сначала верифаер запускает сведение , чтобы получить экземпляр задачи . Будем считать, что доказательство это назначение переменных . Проверять будем случайно выбирая и проверяя, удовлетворяется ли (для этого требуется запросов). Действительно, если , верифаер примет его с вероятностью . Если же , верифаер примет его с вероятностью не больше . Обоснованность может быть увеличена до за счет увеличения количества завпросов к доказательству и использованных случайных бит в константное количество раз.
Стоит заметить, что
-теорема эквивалентна также -трудности задачи .