Изменения

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

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

5 байт добавлено, 18:53, 19 марта 2010
Доказательство
#<tex>A \in P</tex> (что влечёт за собой <tex>SAT \cap A \in NP</tex>);
#<tex>SAT \cap A \not\in P</tex>;
#<tex>SAT \not \leq leqslant SAT \cap A</tex>.
Если такой язык существует, то <tex>L = SAT \cap A</tex> является искомым примером множества
Анонимный участник

Навигация