Изменения
→Доказательство
Докажем, что при условии выполнения равенства <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</tex> — полином.
