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

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

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

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

$\mathrm{EXP} \neq \mathrm{PSPACE}$.

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

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

Предположим, что $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)$.