109
правок
Изменения
→Описание способа построения A
Попытаемся построить такую полиномиальную функцию <tex>f</tex>, что
<tex>A_i = \left\{x \mid f(|x|) = i\right\}</tex>. Тогда
<tex>A=\left\{x \mid f(|x|) \, equiv 0 (\vdots mathrm{mod}\, 2 ) \right\}</tex> и <tex>L=SAT \cap A = \left\{\varphi \mid \varphi \in SAT \land f(|\varphi|)\, equiv 0 (\vdots mathrm{mod}\, 2 ) \right\}</tex>
===Построение <tex>f</tex>===
