143
правки
Изменения
лемма об усилении
* Алфавит: алфавит графа <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>.
Если <tex>UNSAT(G)=0</tex> тогда очевидно <tex>UNSAT(G^t)=0</tex>. Интереснее доказательство того, что <tex>UNSAT(G^t) \ge O(\sqrt{t} \cdot UNSAT(G)</tex>.
{{Лемма
|about=Усиление
|statement= Пусть <tex>\lambda < d</tex> и <tex>|\Sigma|</tex> произвольные константы. Тогда существует константа <tex>\beta_2=\beta_2(\lambda,d,|\Sigma|)>0</rex> такая, что для любого <tex>t \in \mathbb N</tex> и для любого <tex>d</tex>-регулярного графа условий <tex>G=\langle(V,E),\Sigma,\mathcal{C}\rangle</tex> с собственными циклами и <tex>\lambda(G)\le \lambda</tex>,<br/><tex>UNSAT(G^t) \ge \beta_2 \sqrt{t} \cdot min \left({UNSAT(G), \frac 1 t}\right)</tex>.
|proof=TODO
}}
Поскольку <tex>UNSAT(G) \le \frac 1 t</tex>, из жтой леммы следует что <tex>UNSAT(G^t) \ge O(\sqrt{t}) \cdot UNSAT(G)</tex>. Это основная техническая лемма.
===Композиция===
