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