Временная и ёмкостная сложность

Предположим, что $\lim_{n \rightarrow \infty } t_{1}(n) / n=\infty$. Если $t_{1}(n)=t_{2}(n)$ для достаточно больших $n$, то DTIME $\left(t_{1}(n)\right)=\operatorname {DTIME}\left(t_{2}(n)\right)$.

Если $c>1$, то для любого $\epsilon >0, \operatorname {DTIME}(c n)=\operatorname {DTIME}((1+ \epsilon ) n$).

Покажите, что если $A, B \in P$, то $A B \in P$.

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

$\operatorname {PSPACE}\subseteq \operatorname {EXPPOLY}$.

Предположим, что $s(n) \geq \log n$. Докажите, что если машина Тьюринга останавливается на всех входах и имеет ограничение по памяти $s(n)$, то она должна иметь временное ограничение $c^{s(n)}$ для некоторой константы $c$. Используйте этот результат, чтобы показать, что для любого $s(n)$ каждое множество из $\operatorname {DSPACE}(s(n))$ является рекурсивным множеством.

Покажите, что каждое конечное множество строк принадлежит $\operatorname {DTIME}(n)$.

Пусть $A \in \operatorname {DTIME}(f(n))$ и $B \in \operatorname {DTIME}(g(n))$. Докажите, что $A \cup B$ и $A \cap B$ принадлежат $\operatorname {DTIME}(\max \left\{ f(n), g(n)\right\} )$. Сделайте отсюда вывод, что классы сложности $P, \mathrm{PSPACE}, \mathrm{EXP}$ и $\mathrm{EXPPOLY}$ все замкнуты относительно булевых операций объединения, пересечения и дополнения.

В доказательстве теоремы 6.10 мы можем фактически использовать девять шагов $M^{\prime }$ вместо десяти, чтобы смоделировать по крайней мере $m$ шагов $M$. Это можно сделать, объединив четвёртый и пятый шаги в один шаг. Можете ли вы использовать менее девяти шагов в $M^{\prime }$, чтобы выполнить ту же работу?

Оцените, сколько возможных локальных конфигураций существует в доказательстве теоремы 6.10.

Покажите, что каждый контекстно-свободный язык принадлежит $P$ (то есть для каждой контекстно-свободной грамматики существует полиномиальный по времени алгоритм разбора).

Покажите, что если $A$ и $B$ принадлежат $\mathrm{PSPACE}$, то $AB$ и $A^{*}$ также принадлежат $\mathrm{PSPACE}$.

Пусть $A, B \subseteq 1(0+1)^{*}+0$ такие, что каждая строка $x$ из $A$ или $B$ является двоичным представлением натурального числа. Пусть $n(x)$ обозначает натуральное число, чьё двоичное представление есть $x$.