Упражнения

ᴬ Докажите, что $\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\}$.