143
правки
Изменения
Усиление, введение
Под хорошим графом будем понимать регулярный, фиксированной степени экспандер граф.
{{Лемма
|about=Препроцессинг
|statement= существуют константы <tex>0 < \lambda < d</tex> и <tex>\beta_1 >0</tex> такие, что любой граф условий <tex>G</tex> может быть преобразован в граф условий <tex>G'=prep(G)</tex> такой, что:
* <tex>G'</tex> <tex>d</tex>-регулярный
}}
Заметим, что третий пункт теммы гарантирует поддержание полноты, т.е. если <tex>UNSAT(G)=0</tex>, то и <tex>UNSAT(G')=0</tex>. Доказательство этой леммы состоит из двух следующих лемм(<tex>\beta_1=c \cdot \frac d {d + d_0 + 1}</tex>).
{{Лемма
|about=константная Константная степень
|statement=Любой граф условий <tex>G = \langle (V,E),\Sigma,\mathcal{C}\rangle</tex> может быть преобразован в <tex>(d_0 + 1)</tex>-регулярный граф условий <tex>G'=\langle (V',E'),\Sigma,\mathcal{C}'\rangle</tex> такой, что <tex>|V'|</tex>=2|E|</tex> и <tex>c \cdot UNSAT(G) \le UNSAT(G') \le UNSAT(G)</tex>. Для некоторых заданных констант <tex>d_0,c>0</tex>
|proof=TODO
|proof=TODO
}}
===Усиление===
Это новая операция на системах условий, которая увеличивает число неудовлетворенности.
Пусть <tex>G=\langle (V,E),\Sigma,\mathcal{C}\rangle<tex> граф условий, <tex>t \in \mathbb{N}</tex>. Определим <tex>G^t=\langle (V,\mathbf{E}),\Sigma^{d^{\lceil t/2\rceil}}, \mathcal{C}^t \rangle</tex> как следующий граф условий:
* Веришины <tex>G^t</tex> совпадают с вершинами <tex>G</tex>
* Ребра: <tex>u</tex> и <tex>v</tex> соединены <tex>k</tex> ребрами в <tex>\mathbf{E}</tex>, если количество путей длины <tex>t</tex> из <tex>u</tex> в <tex>v</tex> в графе <tex>G</tex> равно <tex>k</tex>
* Алфавит: алфавит графа <tex>G^t</tex> <tex>\Sigma^{d^{\lceil t/2\rceil}}</tex>, где каждой вершине сопоставлены значения ее соседей, достижимых за <tex>\frac t 2</tex> шагов.
* Условия: Условия сопоставленные ребру <tex>e=(u,v) \in \mathbf{E}</tex> удовлетворены, если назначения для <tex>u</tex> и <tex>v</tex> согласованы с назначениями, удовлетворяющими условия, порожденные <tex>\frac t 2</tex> соседями <tex>u</tex> и <tex>v</tex>.
===Композиция===
