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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |definition=<tex>q-CSP</tex> представляет собой <tex>\varphi</tex> — набор функций <tex>\varphi_1, \ld...»)
(нет различий)

Версия 14:22, 2 июня 2012

Определение:
[math]q-CSP[/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\}, такие что \lt tex\gt \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 q-CSP - определить для формулы q-CSP — [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 q-CSP — NP-трудная.