PCP-теорема, альтернативное доказательство

Определение:

[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-трудная.