Изменения

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

1 байт добавлено, 22:29, 11 марта 2010

м

→‎Доказательство

#<math>SAT \nleqslant SAT \cap A</math>.

Если такой язык существует, то <math>L = A SAAT \cap ~~SAT~~A</math> является искомым примером множества

из <math>NP \setminus (P \cup NPC)</math>.

109

правок