Изменения

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

}}

* <tex>size(G')=O(size(G))</tex>

* <tex> \frac d {d + d_0 + 1} \cdot UNSAT(G) \le UNSAT(G') \le UNSAT(G)</tex>

}}