109
правок
Изменения
→Доказательство: добавил два утверждения и условия на A
==Доказательство==
Будем искать такое <math>A</math>, что оно удовлетворяет следующим условиям:
#<math>A \in P</math> (что влечёт за собой<math>SAT \cap A \in NP</math>)
#<math>SAT \cap A \not\in P</math>
#<math>SAT \nleqslant SAT \cap A</math>
'''Утверждение 1.''' Можно перечислить (возможно с повторениями) все языки из <math>P</math>
Действительно, рассмотрим последовательность всех программ
<math> \tilde{p_1}, \tilde{p_2}, \ldots, \tilde{p_n}, \ldots</math>
Обозначим за <math>p_i</math> программу, запускающую <math>\tilde{p_i}</math>
с таймером <math>in^i</math>. Тогда среди <math>{p_i}</math> встречаются
только программы из <math>P</math>, и для каждой полиномиальной программы
<math>\tilde{p_i}</math>, работающей за полином <math>q_i(n)</math>, существует
номер <math>j</math>, такой что <math>jn^j > g_i(n)</math> для всех натуральных <math>n</math>
и <math>\tilde{p_j}</math> делает то же самое, что и <math>\tilde{p_i}</math>.
Таким образом <math>p_j</math> распознает тот же язык, что и <math>\tilde{p_i}</math>.
'''Утверждение 2.''' Можно перечислить все функции из <math>\tilde{P}</math>.
Доказательство аналогично доказательству предыдущего утверждения.
<math>L=\left\{\varphi | \varphi \in SAT \and f(|\varphi|) \text{ is even}\right\}</math>
<math>f(0) = f(1) = 0</math>
Определим <math>f(n)</math>. Для этого рассмотрим два случая:
*'''Случай 1:''' <math>f(n-1)=2i</math>.
*: Если существует <math>x</math>, такой что <math>|x| < \log_2n</math> и <math>M_i(x) \ne L(x)</math>, то <math>f(n) = f(n-1)+1</math>, иначе <math>f(n) = f(n-1)</math>.
*'''Случай 2:''' <math>f(n-1)=2i+1</math>.
*:Если существует <math>x</math>, такой что <math>|x| < \log_2n</math> и <math>SAT(x) \ne L(g_i(x))</math>, то <math>f(n) = f(n-1)+1</math>, иначе <math>f(n) = f(n-1)</math>.
