Изменения

|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>.

}}

Поскольку <tex>UNSAT(G) \le \frac 1 t</tex>, из жтой леммы следует что <tex>UNSAT(G^t) \ge O(\sqrt{t}) \cdot UNSAT(G)</tex>. Это основная техническая лемма.

===Композиция===

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