Изменения
Новая страница: «{{Определение |definition=<tex>q-CSP</tex> представляет собой <tex>\varphi</tex> — набор функций <tex>\varphi_1, \ld...»
{{Определение
|definition=<tex>q-CSP</tex> представляет собой <tex>\varphi</tex> — набор функций <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>.
Назовём распределение <tex>u \in \{0, 1\}</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> - удовлетворима.
}}
{{Определение
|definition=<tex>\rho \in (0, 1)</tex>. Задача <tex>\rho</tex>-GAP q-CSP - определить для формулы q-CSP — <tex>\varphi</tex>:
<tex>\bullet</tex> <tex>\varphi</tex> удовлетворима, то "YES".
<tex>\bullet</tex> <tex>val(\varphi) \leq \rho</tex>, то "NO".
}}
{{Теорема
|statement=Существуют <tex>q \in \mathbb{N}, \rho \in (0, 1)</tex> такие, что задача <tex>\rho</tex>-GAP q-CSP — NP-трудная.
}}
|definition=<tex>q-CSP</tex> представляет собой <tex>\varphi</tex> — набор функций <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>.
Назовём распределение <tex>u \in \{0, 1\}</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> - удовлетворима.
}}
{{Определение
|definition=<tex>\rho \in (0, 1)</tex>. Задача <tex>\rho</tex>-GAP q-CSP - определить для формулы q-CSP — <tex>\varphi</tex>:
<tex>\bullet</tex> <tex>\varphi</tex> удовлетворима, то "YES".
<tex>\bullet</tex> <tex>val(\varphi) \leq \rho</tex>, то "NO".
}}
{{Теорема
|statement=Существуют <tex>q \in \mathbb{N}, \rho \in (0, 1)</tex> такие, что задача <tex>\rho</tex>-GAP q-CSP — NP-трудная.
}}
