Труднорешаемость

ᴬ Докажите, что $\operatorname {TIME}\left(2^{n}\right)=\operatorname {TIME}\left(2^{n+1}\right)$.

ᴬ Докажите, что $\operatorname {TIME}\left(2^{n}\right) \subsetneq \operatorname {TIME}\left(2^{2 n}\right)$.

ᴬ Докажите, что $\operatorname {NTIME}(n) \subsetneq \operatorname {PSPACE}$.

Покажите, как схема, изображённая на рисунке 9.26, работает на входе 0110, приведя значения, вычисляемые всеми вентилями, как мы делали на рисунке 9.24.

Приведите схему, вычисляющую функцию чётности от трёх входных переменных, и покажите, как она работает на входе 011.

Докажите, что если $A \in \mathrm{P}$, то $\mathrm{P}^{A}=\mathrm{P}$.

Приведите регулярные выражения с возведением в степень, порождающие следующие языки над алфавитом $\left\{ 0,1\right\}$.

Если $R$ — регулярное выражение, пусть $R^{\left\{ m, n\right\} }$ обозначает выражение

Покажите, как реализовать оператор $R^{\left\{ m, n\right\} }$, используя обычный оператор возведения в степень, но без «…».

Покажите, что если $\mathrm{NP}=\mathrm{P}^{\text{SAT }}$, то $\mathrm{NP}=$ coNP.

В задаче 8.13 было показано, что $A_{\text{LBA }}$ PSPACE-полна.

Покажите, что язык MAX-CLIQUE из задачи 7.48 принадлежит $\mathrm{P}^{\text{SAT }}$.

Задача 7.48: MAX-CLIQUE $=\left\{ \langle G, k\rangle \mid \text{ наибольшая клика в }G\text{ имеет размер ровно }k\right\}$.

Опишите ошибку в следующем ошибочном «доказательстве» того, что $\mathrm{P} \neq \mathrm{NP}$. Предположим, что $\mathrm{P}=\mathrm{NP}$, и придём к противоречию. Если $\mathrm{P}=\mathrm{NP}$, то $S A T \in \mathrm{P}$, и потому при некотором $k$, $S A T \in \operatorname {TIME}\left(n^{k}\right)$. Поскольку каждый язык из NP сводится к $S A T$ за полиномиальное время, получаем $\mathrm{NP} \subseteq \operatorname {TIME}\left(n^{k}\right)$. Следовательно, $\mathrm{P} \subseteq \operatorname {TIME}\left(n^{k}\right)$. Но по теореме об иерархии по времени, $\operatorname {TIME}\left(n^{k+1}\right)$ содержит язык, не принадлежащий $\operatorname {TIME}\left(n^{k}\right)$, что противоречит $\mathrm{P} \subseteq \operatorname {TIME}\left(n^{k}\right)$. Следовательно, $\mathrm{P} \neq \mathrm{NP}$.

Рассмотрим функцию pad : $\Sigma^{*} \times \mathcal{N} \longrightarrow \Sigma^{*} \#^{*}$, определённую следующим образом. Пусть $\operatorname {pad}(s, l)=s \#^{j}$, где $j=\max (0, l-m)$, а $m$ — длина $s$. Таким образом, $\operatorname {pad}(s, l)$ просто добавляет к концу $s$ достаточно много копий нового символа , чтобы длина результата была не менее $l$. Для произвольного языка $A$ и функции $f: \mathcal{N} \longrightarrow \mathcal{N}$ определим язык $\operatorname {pad}(A, f)$ как

Докажите, что если $A \in \operatorname {TIME}\left(n^{6}\right)$, то $\operatorname {pad}\left(A, n^{2}\right) \in \operatorname {TIME}\left(n^{3}\right)$.

Докажите, что если NEXPTIME $\neq$ EXPTIME, то $\mathrm{P} \neq \mathrm{NP}$. Вам может пригодиться функция pad, определённая в задаче 9.13.

ᴬ Определим pad, как в задаче 9.13.

Задача 9.13: Рассмотрим функцию pad : $\Sigma^{*} \times \mathcal{N} \longrightarrow \Sigma^{*} \#^{*}$, определённую следующим образом. Пусть $\operatorname {pad}(s, l)=s \#^{j}$, где $j=\max (0, l-m)$, а $m$ — длина $s$. Таким образом, $\operatorname {pad}(s, l)$ просто добавляет к концу $s$ достаточно много копий нового символа , чтобы длина результата была не менее $l$. Для произвольного языка $A$ и функции $f: \mathcal{N} \longrightarrow \mathcal{N}$ определим язык $\operatorname {pad}(A, f)$ как

Докажите, что $T Q B F \notin \operatorname {SPACE}\left(n^{1 / 3}\right)$.

• Вспомните определение 2DFA (двухголовочного конечного автомата), приведённое в задаче 5.26. Докажите, что P содержит язык, не распознаваемый никаким 2DFA.

Задача 5.26: Двухголовочный конечный автомат (2DFA) — это детерминированный конечный автомат с двумя доступными только для чтения двунаправленными головками, которые начинают работу с левого конца входной ленты и могут независимо перемещаться в любом направлении. Лента 2DFA конечна и имеет размер, достаточный лишь для размещения входных данных плюс две дополнительные пустые ячейки ленты — по одной с каждого конца — служащие разделителями. 2DFA допускает входную строку, переходя в специальное допускающее состояние.

Пусть $E_{\text{REX } \uparrow }=\left\{ \langle R\rangle \mid R\text{ — регулярное выражение с возведением в степень и }L(R)=\emptyset \right\}$. Покажите, что $E_{\text{REX } \uparrow } \in$ P.

Определим задачу об однозначной выполнимости как

Покажите, что USAT $\in \mathrm{P}^{S A T}$.

Докажите, что существует оракул $C$, для которого $\mathrm{NP}^{C} \neq \operatorname {coNP}^{C}$.

Машиной Тьюринга с оракулом и $k$ запросами называется машина Тьюринга с оракулом, которой разрешено делать не более $k$ запросов на каждом входе. Машина Тьюринга с оракулом для $A$ и $k$ запросами обозначается $M^{A, k}$. Определим $\mathrm{P}^{A, k}$ как совокупность языков, разрешаемых полиномиальными по времени машинами Тьюринга с оракулом для $A$ и $k$ запросами.

Предположим, что $A$ и $B$ — два оракула. Один из них — оракул для $T Q B F$, но вы не знаете, какой именно. Приведите алгоритм, имеющий доступ и к $A$, и к $B$, который гарантированно решает TQBF за полиномиальное время.

Напомним, что можно рассматривать схемы, выдающие строки над $\left\{ 0,1\right\}$, выделив несколько выходных вентилей. Пусть $\operatorname {add}_{n}:\left\{ 0,1\right\}^{2 n} \longrightarrow \left\{ 0,1\right\}^{n+1}$ принимает два $n$-битовых двоичных целых числа и выдаёт их $(n+1)$-битовую сумму. Покажите, что функцию add$_{n}$ можно вычислить схемами размера $O(n)$.

Определим функцию $\operatorname {majority}_{n}:\left\{ 0,1\right\}^{n} \longrightarrow \left\{ 0,1\right\}$ как

Таким образом, функция $\operatorname {majority}_{n}$ возвращает результат голосования большинства входов. Покажите, что $\operatorname {majority}_{n}$ можно вычислить:

• Определим функцию $\operatorname {majority}_{n}$, как в задаче 9.24. Покажите, что её можно вычислить схемами размера $O(n)$.

Задача 9.24: Функция $\operatorname {majority}_{n}:\left\{ 0,1\right\}^{n} \longrightarrow \left\{ 0,1\right\}$ определяется как

Таким образом, функция $\operatorname {majority}_{n}$ возвращает результат голосования большинством по входным значениям.