Теоремы об иерархии

Покажите, что $(n+2)^{2}$ полностью конструктивна по времени.

Покажите, что $\lceil \sqrt{n}\rceil$ полностью конструктивна по памяти.

$\quad P \underset {\neq }{\subset } EXP$.

$EXP \neq PSPACE$.

Опишите подробно ДМТ с 3 рабочими лентами $M^{*}$ из теоремы 6.16. В частности, опишите, как $M^{*}$ работает, используя вход $w$ одновременно как машинный код для $M_{w}$ и как вход для $M_{w}$, в то время как он хранится на входной ленте только для чтения.

В доказательстве теоремы 6.17 мы использовали технику чередования, чтобы выполнить параллельное моделирование $M_{w}$ и $M^{c}$. Можем ли мы вместо этого использовать метод произведения машин Тьюринга из примера 5.9, чтобы выполнить параллельное моделирование?

($M_{w}$ обозначает ДМТ, чей код есть $w$, а $M^{c}$ — это фиксированная часовая машина $t_{2}(n)$, используемая в доказательстве: ДМТ, которая останавливается ровно за $t_{2}(n)$ шагов на любом входе длины $n$. Там метод чередования означает поочерёдное моделирование одного шага $M_{w}$ и одного шага $M^{c}$, с остановкой, как только останавливается любая из них. Метод произведения машин Тьюринга из примера 5.9, напротив, строит единую новую ДМТ, состояния которой — пары $(q_{i}, q_{j})$, по одному состоянию из каждой из двух фиксированных машин $M_{n}, M_{m}$, с объединённой функцией переходов $\delta$, построенной механически из функций переходов $\delta_{n}, \delta_{m}$ самих машин $M_{n}$ и $M_{m}$.)

Предположим, что $A \leq_{m} B$ через функцию сведения $f$ с временным ограничением $2^{n}$. Также предположим, что $B \in \operatorname {DTIME}(2^{n})$. Что можно сказать о временной сложности множества $A$?

Покажите, что $\operatorname {DSPACE}\left(n\left(\log^{*} n\right)^{100}\right) \stackrel{\subset }{\neq } \operatorname {DSPACE}(n \log n)$.

Покажите, что EXP $\underset {\neq }{\subsetneq }$ EXPPOLY.

Покажите, что PSPACE $\underset {\neq }{\cup } \bigcup_{c>0} \operatorname {DSPACE}\left(2^{c n}\right)$.