53
правки
Изменения
Нет описания правки
==Доказательство==
Будем искать язык <tex>A</tex>, удовлетворяющий следующим условиям:
#<tex>A \in P</tex> (что влечёт за собой<tex>SAT \cap A \in NP</tex>);
#<tex>SAT \cap A \not\in P</tex>;
#<tex>SAT \not \leq SAT \cap A</tex>.
Попытаемся построить такую полиномиальную функцию <tex>f</tex>, что
<tex>A_i = \left\{x \mid f(|x|) = i\right\}</tex>. Тогда
<mathtex>A=\left\{x \mid f(|x|) \, \vdots \, 2 \right\}</mathtex> и
<math>L=SAT \cap A = \left\{\varphi \mid \varphi \in SAT \and f(|\varphi|)\, \vdots \, 2\right\}</math>
