Изменения

Будем искать такое язык <math>A</math>, что оно удовлетворяет удовлетворяющий следующим условиям:

Если такой язык существует, то <math>L = A \cap SAT</math> искомым примером множестваиз <math>NP \setminus (P \cup NPC)</math>. '''Утверждение 1.''' Можно перечислить (возможно с повторениями) все языки из <math>P</math>.

*: Если существует <math>x</math>, такой что <math>|x| < \log_2nlog_2 n</math> и <math>M_ip_i(x) \ne L(x)</math>, то <math>f(n) = f(n-1)+1</math>, иначе <math>f(n) = f(n-1)</math>.

*:Если существует <math>x</math>, такой что <math>|x| < \log_2nlog_2 n</math> и <math>SAT(x) \ne L(g_if_i(x))</math>, то <math>f(n) = f(n-1)+1</math>, иначе <math>f(n) = f(n-1)</math>. Покажем, что <math>f \in \tilde{P}</math>. Для упрощения будем считать, что алфавит <math>\Sigma={0,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_1(n)</math> — построение программы <math>f_i</math>. <math>a(n) \approx 2^{log_2 n} = n</math>, таким образом <math>a(n) \in \tilde{P}</math> <math>b_1(n) \approx</math> что-то, тоже из <math>\tilde{P}</math> <math>b_2(n) \approx 2^{log_2 n} log_2 n </math>, из <math>\tilde{P}</math> <math>b_3(n) \approx 2^{log_2 n} log_2 n + log_2 n</math>, из <math>\tilde{P}</math> <math>b_4(n) \approx </math> что-то типа <math>b_3(n)</math>, но с оценкой на <math>|f_i(x)|</math>вместо <math>log_2 n</math>, из <math>\tilde{P}</math> <math>c_1(n)</math> и <math>c_2(n)</math> тоже полиномиальны. Получаем, что <math>T(n) = T(n-1) + poly</math>. Значит <math>T(n) \le n \cdot poly </math>. Поэтому <math>T(n) \in \tilde{P}</math> и <math>A \in P</math>. В результате всё почти хорошо. Теорема доказана.