Изменения

Пусть <tex>T_gT^g(n)</tex> — время вычисления <tex>g(n)</tex>.

<tex>T_2(n) \le c_2 n (|x|^i + T_gT^g(|x|) + 2^{|x|}|x|)</tex>

<tex>T_2(n) \le c_2 n (log_2^{i} n + T_gT^g(|x|) + 2^{log_2 n} log_2 n)</tex>

<tex>T_2(n) \le c_2 n (log_2^{g(n)} n + T_gT^g(log_2 n) + n log_2 n)</tex>

<tex>T_2(n) \le c_2 (n^2 + n^2 log_2 n + n T_gT^g(log_2 n))</tex>

<tex>T_2(n) \le c_2 (2n^3 + n T_gT^g(log_2 n))</tex>

<tex>T_3(n) \le 2^{log_2 n} (T(x \in \mathrm{SAT}) + T_gT^g(|f_i(x)|) + T(f_i(x) \in \mathrm{SAT}))</tex>

<tex>T_3(n) \le c_3 n (2^{log_2 n} log_2 n + T_gT^g(log_2 n) + 2^{log_2 n} log_2 n)</tex>

<tex>T_3(n) \le c_3 (2n^2 log_2 n + n T_gT^g(log_2 n))</tex>

<tex>T_3(n) \le c_3 (2n^3 + n T_gT^g(log_2 n))</tex>

<tex>T_gT^g(n) \le T_gT^g(n-1) + c_1 n^5 + c_2 (2n^3 + n T_gT^g(log_2 n)) + c_3 (2n^3 + n T_gT^g(log_2 n))</tex>

<tex>T_gT^g(n) \le T_gT^g(n-1) + k_1 n^5 + k_2 n T_gT^g(log_2 n)</tex>

Пусть <tex>T_gT^g(1) = const = d</tex>. Существует константа <tex>c \ge d</tex>, для которой при любом <tex>n</tex> верно

Тогда, в силу <tex>T_gT^g(1) = d \le c 1^7</tex> и неравенства выше, по индукции легко доказать, что <tex>T_gT^g(n)</tex> ограничено сверху <tex>c n^7</tex>, то есть <tex>g \in \tilde{\mathrm{P}}</tex>, а, в свою очередь, <tex>A \in \mathrm{P}</tex>.