Изменения
Новая страница: «=== Формулировка === :<tex>\text{P=NP} \Rightarrow \text{EXP=NEXP}</tex> === Доказательство === Рассмотрим <tex>\text{NEXP---}</…»
=== Формулировка ===
:<tex>\text{P=NP} \Rightarrow \text{EXP=NEXP}</tex>
=== Доказательство ===
Рассмотрим <tex>\text{NEXP---}</tex> полный язык <tex>\text{BH}_{2N}=\{\langle m, x, t \rangle ~|~ m(x)=1, T(m, x) \le t \}</tex>.
Докажем, что при условии выполнения равенства <tex>\text{P=NP,~BH}_{2N} \in \text{EXP}</tex>.
Сведем <tex>\text{BH}_{2N}</tex> к <tex>\text{BH}_{1N}</tex> по Карпу за экпоненциальное время <tex>\left( \text{BH}_{2N} \le_{\tiny{\text{EXP}}} \text{BH}_1N \right)</tex>.
Для этого запишем <tex>\text{t}</tex> в унарной системе счисления: <tex>\langle m, x, t \rangle \rightarrow \langle m, x, 1^t \rangle</tex>.
Ясно, что для выполнение этого сведения потребуется выполнить <tex>O(2^{p_1(t)})</tex> операций, где <tex>p_1\text{---}</tex> полином.
Поскольку мы предположили, что <tex>\text{P=NP}</tex>, то существует детерминированная машина Тьюринга <tex>M</tex>, разрешающая <tex>\text{BH}_{1N}</tex> за полиномиальное от длины
входа время <tex>\left( T(M, \langle m, x, 1^t \rangle) ~=~ O(p_2(|\langle m, x, 1^t \rangle|)),~ p_2 \in \text{\textit{\large{poly}}} \right)</tex>. Имея ее, легко построить машину <tex>M'</tex>, которая сначала выполняла бы описанное выше сведение, а затем подавала бы полученный результат на вход машине <tex>M</tex>. То есть <tex>M'(\langle m, x, t \rangle) ~=~ M(\langle m, x, 1^t \rangle)</tex>.
Заметим, что время работы машины <tex>M'</tex> складывается из времени, необходимого на преобразование входа, и времени работы машины <tex>M</tex>.
:<tex>T(M', \langle m, x, t \rangle) ~=~ O(2^{p_1(t)}) + O(p_2(|\langle m, x, 1^t \rangle|)) = O(2^{poly(|\langle m, x, t \rangle|)})</tex>
Полученное равенство означает, что <tex>\text{BH}_{2N} \in \text{EXP}</tex>, откуда в силу [[NEXP-полнота|NEXP-полноты]] языка <tex>\text{BH}_{2N}</tex> вытекает включение <tex>\text{NEXP} \subset \text{EXP}</tex>. Поскольку обратное включение <tex>\left(\text{NEXP} \supset \text{EXP}\right)</tex> тривиально, то это и означает, что <tex>\text{EXP=NEXP}</tex>
:<tex>\text{P=NP} \Rightarrow \text{EXP=NEXP}</tex>
=== Доказательство ===
Рассмотрим <tex>\text{NEXP---}</tex> полный язык <tex>\text{BH}_{2N}=\{\langle m, x, t \rangle ~|~ m(x)=1, T(m, x) \le t \}</tex>.
Докажем, что при условии выполнения равенства <tex>\text{P=NP,~BH}_{2N} \in \text{EXP}</tex>.
Сведем <tex>\text{BH}_{2N}</tex> к <tex>\text{BH}_{1N}</tex> по Карпу за экпоненциальное время <tex>\left( \text{BH}_{2N} \le_{\tiny{\text{EXP}}} \text{BH}_1N \right)</tex>.
Для этого запишем <tex>\text{t}</tex> в унарной системе счисления: <tex>\langle m, x, t \rangle \rightarrow \langle m, x, 1^t \rangle</tex>.
Ясно, что для выполнение этого сведения потребуется выполнить <tex>O(2^{p_1(t)})</tex> операций, где <tex>p_1\text{---}</tex> полином.
Поскольку мы предположили, что <tex>\text{P=NP}</tex>, то существует детерминированная машина Тьюринга <tex>M</tex>, разрешающая <tex>\text{BH}_{1N}</tex> за полиномиальное от длины
входа время <tex>\left( T(M, \langle m, x, 1^t \rangle) ~=~ O(p_2(|\langle m, x, 1^t \rangle|)),~ p_2 \in \text{\textit{\large{poly}}} \right)</tex>. Имея ее, легко построить машину <tex>M'</tex>, которая сначала выполняла бы описанное выше сведение, а затем подавала бы полученный результат на вход машине <tex>M</tex>. То есть <tex>M'(\langle m, x, t \rangle) ~=~ M(\langle m, x, 1^t \rangle)</tex>.
Заметим, что время работы машины <tex>M'</tex> складывается из времени, необходимого на преобразование входа, и времени работы машины <tex>M</tex>.
:<tex>T(M', \langle m, x, t \rangle) ~=~ O(2^{p_1(t)}) + O(p_2(|\langle m, x, 1^t \rangle|)) = O(2^{poly(|\langle m, x, t \rangle|)})</tex>
Полученное равенство означает, что <tex>\text{BH}_{2N} \in \text{EXP}</tex>, откуда в силу [[NEXP-полнота|NEXP-полноты]] языка <tex>\text{BH}_{2N}</tex> вытекает включение <tex>\text{NEXP} \subset \text{EXP}</tex>. Поскольку обратное включение <tex>\left(\text{NEXP} \supset \text{EXP}\right)</tex> тривиально, то это и означает, что <tex>\text{EXP=NEXP}</tex>
