109
правок
Изменения
→Доказательство: исправлено немного ошибок
Будем искать язык <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>.
Если такой язык существует, то <math>L = A \cap SAT</math> является искомым примером множества
из <math>NP \setminus (P \cup NPC)</math>.
'''Утверждение 1.''' Можно перечислить (возможно с повторениями) все языки из <math>P</math>.
Действительно, рассмотрим последовательность всех программ, упорядоченных по длине,:
<math> \tilde{p_0}, \tilde{p_1}, \ldots, \tilde{p_n}, \ldots</math>
Обозначим за <math>p_i</math> программу, запускающую <math>\tilde{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>\tilde{f_i}</math>,
а затем, добавив таймер <math>in^i</math>, получим последовательность <math>f_i</math>.
так, что <math>SAT \cap \bigcup_{i=0}^{k} A_{2i}</math> отличается от <math>L(p_k)</math> элементом
из <math>\bigcup_{i=0}^{2k} A_i</math>, и существует <math>\alpha \in \bigcup_{i=0}^{2k+1}</math>
для которого выполняется условие условия <math>f(\alpha) \in \bigcup_{i=0}^{2k+1}</math> и
<math>[\alpha \in SAT] \ne [f(\alpha) \in SAT \cap \bigcup_{i=0}^{k} A_{2i}]</math>.
Если мы сможем построить такие <math>A_i</math>, то язык <math>L = SAT \cap \bigcup_{i=0}^{\infty} A_{2i}</math>
будет отличаться от любого полиномиального языка , и ни какая полиномиальная функция не будет сводить
<math>SAT</math> к <math>L</math>.
<math>L=SAT \cap A = \left\{\varphi \mid \varphi \in SAT \and f(|\varphi|)\, \vdots \, 2\right\}</math>
Зададим <math>f(0) = f(1) = 0</math>. Теперь Затем рекурсивно определим <math>f(n)</math>. Для этого рассмотрим три случая:#<math>{\log_2 n} ^ {f(n-1)} \ge n</math>.:#:<math>f(n) = f(n-1)</math>.;#<math>f(n-1)=2i</math>.:#:Если существует <math>x</math>, такой что <math>|x| < \log_2 n</math> и <math>p_i(x) \ne L(x)</math>, то <math>f(n) = f(n-1)+1</math>, иначе <math>f(n) = f(n-1)</math>.;#<math>f(n-1)=2i+1</math>.:
#:Если существует <math>x</math>, такой что <math>|x| < \log_2 n</math> и <math>SAT(x) \ne L(f_i(x))</math>, то <math>f(n) = f(n-1)+1</math>, иначе <math>f(n) = f(n-1)</math>.
<math>T(n) = T(n-1) + a(n)(b_1(n) + b_2(n) + b_3(n) + b_4(n)) + c_1(n) + c2_2(n)</math>, где:
*<math>T(n-1)</math> идёт на вычисление <math>f(n-1)</math>;
*<math>a(n)</math> — перебор время перебора всех слов <math>x</math>, таких что <math>|x| < \log_2 n</math>;*<math>b_1(n)</math> — запуск время работы <math>p_i(x)</math>;*<math>b_2(n)</math> — запуск время работы <math>SAT(x)</math>;*<math>b_3(n)</math> — запуск время работы <math>L(x)</math>;*<math>b_4(n)</math> — запуск время работы <math>L(f_i(x))</math>;*<math>c_1(n)</math> — построение время, необходимое для построения программы <math>p_i</math>;*<math>c_2(n)</math> — построение программы время, необходимое для построения функции <math>f_i</math>.
<math>a(n) = O\left(2^{\log_2 n}\right) = O(n)</math>, таким образом <math>a(n) \in \tilde{P}</math>.
<math>b_1(n) = O\left((i(\log_2 n)^i\right) = O\left(f(n-1)(\log_2 n)^{f(n-1)}\right) = O\left(f(n-1)n\right) = O(n^2) \in \tilde{P}</math>
Из того, что все <math>\tilde{p_i}</math> упорядоченны по длине, следует, что длина
<math>\tilde{p_i}</math> не превосходит <math>ci</math> (константа зависит от языка описания программы).
Поэтому для построения i-ой программы достаточно перебрать все <math>2^{ci+1}-1</math> слов с длиной меньше, чем не больше <math>ci</math>,
и вывести i-ое, являющееся программой. Такой способ требует <math>O(2^{ci}i) = O(2^{\log_2 n} \log_2 n) = O(n^2)</math> времени.
Аналогично можно построить и <math>f_i</math>. Из этого следует, что <math>c_1(n)</math> и <math>c_2(n)</math> тоже полиномиальны.
