109
правок
Изменения
м
→Описание способа построения A
===Описание способа построения <math>A</math>===
Упорядочим все слова по возрастанию длины. Разобьем всё <tex>\Sigma^{*}</tex> на множества
<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>x_{2k+1} \in \bigcup_{i=0}^{2k+1} A_i</tex>,
для которого выполняются условия <tex>f_k(x_{2k+1}) \in \bigcup_{i=0}^{2k+1} A_i</tex> и
<tex>[x_{2k+1} \in SAT] \ne [f_k(x_{2k+1}) \in SAT \cap \bigcup_{i=0}^{k} A_{2i}]</tex>.
<tex>A_i = \left\{x \mid f(|x|) = i\right\}</tex>. Тогда
<tex>A=\left\{x \mid f(|x|) \, \vdots \, 2 \right\}</tex> и
<mathtex>L=SAT \cap A = \left\{\varphi \mid \varphi \in SAT \and land f(|\varphi|)\, \vdots \, 2\right\}</mathtex>
===Построение <tex>f</tex>===
