171
правка
Изменения
м
* <tex>T(n) \le 2^{\log_2 n} (T(M_i, x) + T(g, |x|) + T(nx \in \mathrm{SAT})) = 2i</tex>:;
* <tex>T(n) \le k_2 n (2^{\log_2 n} \log_2 n + T(g(, \log_2 n) = 2i + 12^{\log_2 n} \log_2 n)</tex>:;
Нет описания правки
Если выполнены все три свойства, то <tex>L \in \mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC})</tex>.
Пусть <tex>M_1, \ldots, M_n, \ldots</tex> — все машины Тьюринга из <tex>\tilde{\mathrm{P}}</tex>, причём <tex>T(M_i(, x)) \le |x|^i</tex> для любого <tex>x \in \Sigma^*</tex>.
Пусть <tex>f_1, \ldots, f_n, \ldots</tex> — аналогичное множество полиномиальных функций: <tex>T(f_i(, x)) \le |x|^i</tex> для любого <tex>x \in \Sigma^*</tex>.
Для простоты будем считать, что <tex>|\Sigma| = 2</tex>. Построим такую ''неубывающую'' функцию <tex>g \in \tilde{\mathrm{P}}</tex>, что для <tex>A = \{x \in \Sigma^*: g(|x|) \equiv 0 \pmod{2} \}</tex> выполняются три перечисленных свойства.
=== Время работы алгоритма ===
Проверим первое свойство — полиномиальность выполнение первого свойства языка <tex>AL</tex>. Пусть Для этого достаточно установить полиномиальность <tex>T^g(n)</tex> — время вычисления <tex>g(n)A</tex>.
Заметим, что <tex>g(n) \le n</tex> по построению для <tex>n \ge 1</tex>.
Время выполнения шагов составляет:
* проверка неравенства: для случая <tex>T_1(n) \le g(n) T_*(\log_2^{g(n)} n, \log_2^{g(n)} n)</tex> <tex>T_1(n) \le c_1 g(n) (\log_2 (\log_2^{g(n)} n))^2</tex> <tex>T_1(n) \le c_1 g^3(n) \log_2^2 \log_2 n</tex> <tex>T_1(n) \le c_1 n^3 \log_2^2 \log_2 n</tex> <tex>T_1(n) \le c_1 n^5</tex>, где <tex>T_*(a, b)</tex> — время нахождения произведения чисел <tex>a</tex> и <tex>b= 2i</tex>:
<tex>T_2T(n) \le 2^{\log_2 k_1 n} (T(M_i(|x)) |^i + T(g(, |x|)) + T(2^{|x \in \mathrm{SAT|})|x|)</tex>;
<tex>T_2T(n) \le c_2 k_1 n (|x|(\log_2 n)^i {g(n)} + T^(g(|x|, \log_2 n) + 2^{|x|\log_2 n}|x|\log_2 n)</tex>;
<tex>T_2T(n) \le c_2 k_1 (n (\log_2^{i} 2 + n + T^g(|x|) + 2^{\log_2 n} + n T(g, \log_2 n))</tex>;
<tex>T_2T(n) \le c_2 n k_1 (\log_22n^{g(n)} 3 + n + T^(g(, \log_2 n) + n \log_2 n)</tex>;
* для случая <tex>T_2g(n) \le c_2 (n^2 + n^2 \log_2 n = 2i + n T^g(\log_2 n))1</tex>:
<tex>T_2T(n) \le c_2 2^{\log_2 n} (T(2n^3 x \in \mathrm{SAT}) + n T^(g, |f_i(x)|) + T(f_i(x) \in \log_2 nmathrm{SAT}))</tex>;
<tex>T_3T(n) \le k_2 (2n^2^{\log_2 n} (+ n T(x \in \mathrm{SAT}) + T^g(|f_i(x)|) + T(f_i(x) , \in \mathrm{SAT}log_2 n))</tex>;
<tex>T_3T(n) \le c_3 n k_2 (22n^{\log_2 3 + n} \log_2 n + T^(g(, \log_2 n) + 2^{\log_2 n} \log_2 n)</tex>.
Кроме того, необходимо знать значение <tex>T_3g(n) \le c_3 </tex>, получаемое на <tex>n-1</tex> шаге, и вычислить <tex>(2n^2 \log_2 n + n T)^{g(\log_2 n))}</tex>, что можно сделать за
<tex>T_3k_3 \log_2 g(n) |(\le c_3 log_2 n)^{g(2n^3 + n T)}|^2 \le k_3 (g(\n) |log_2 n|))^2 log_2 n \le k_3 n^3</tex>.
Таким образом,
<tex>T^(g(, n) \le T^(g(, n-1) + c_1 k (n^5 + c_2 (2n^3 + n T^g(\log_2 n)) + c_3 (2n^3 + n T^g(, \log_2 n))</tex> <tex>T^g(n) \le T^g(n-1) + k_1 n^5 + k_2 n T^g(\log_2 n)</tex>.
Пусть <tex>T^(g(, 1) = const = d</tex>. Существует константа <tex>c \ge d</tex>, для которой при любом <tex>n</tex> верно
<tex>c (n-1)^7 4 + k_1 k n^5 3 + k_2 k n c (\log_2 n)^7 4 \le c n^74</tex>.
Тогда, в силу <tex>T^(g(, 1) = d \le c \cdot 1^74</tex> и неравенства выше, по индукции легко доказать, что <tex>T^(g(, n)</tex> ограничено сверху <tex>c n^74</tex>, то есть <tex>g \in \tilde{\mathrm{P}}</tex>, а, в свою очередь, <tex>A \in \mathrm{P}</tex>.
}}
