Изменения

Перейти к: навигация, поиск

Теорема Ладнера

1 байт убрано, 16:25, 19 марта 2010
Описание способа построения A
Упорядочим все слова по возрастанию длины. Разобьем всё <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>.
[[File:Ladner.png]]
109
правок

Навигация