109
правок
Изменения
→Описание способа построения A: добавил рисунок
<tex>A_i</tex> так, что <tex>\forall i<j, \forall \alpha \in A_i, \beta \in A_j: |\alpha| < |\beta|</tex>
(то есть разбиение происходит по длинам, причем <tex>A_i</tex> идут «подряд»),
<tex>SAT \cap \bigcup_{i=0}^{k} A_{2i}</tex> отличается от <tex>L(p_k)</tex> элементом<tex>x_{2k}</tex>из <tex>\bigcup_{i=0}^{2k} A_i</tex> и для любого <tex>k</tex> существует <tex>\alpha x_{2k+1} \in \bigcup_{i=0}^{2k+1} A_i</tex>,для которого выполняются условия <tex>f_k(\alphax_{2k+1}) \in \bigcup_{i=0}^{2k+1} A_i</tex> и <tex>[\alpha x_{2k+1} \in SAT] \ne [f_k(\alphax_{2k+1}) \in SAT \cap \bigcup_{i=0}^{k} A_{2i}]</tex>.
Если мы сможем построить такие <tex>A_i</tex>, то язык <tex>L = SAT \cap \bigcup_{i=0}^{\infty} A_{2i}</tex>
