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

Предположим, что $\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, PSPACE, EXP$ и $EXPPOLY$ все замкнуты относительно булевых операций объединения, пересечения и дополнения.

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

(В доказательстве теоремы 6.10 каждый шаг моделирования $M^{\prime }$ занимает десять шагов, управляемых локальным счётчиком $j \in \left\{ 0,1,\cdots ,9\right\}$, входящим в состояние. Обозначим через $g$ ячейку, сканируемую в данный момент, а через $r, \ell$ — её правого и левого соседей: шаги $1$–$4$ образуют пчелиный танец, считывающий символы $r$ и $\ell$ в состояние — сдвиг вправо к $r$, сдвиг влево обратно к $g$, сдвиг влево к $\ell$, сдвиг вправо обратно к $g$; шаг $5$ моделирует $M$ на полученной локальной конфигурации как можно большее число шагов — это чисто внутреннее изменение состояния без движения головки; шаги $6$–$9$ — второй пчелиный танец, копирующий обновлённые символы обратно в ячейки $\ell , g, r$; а шаг $10$ передвигает головку к одному из соседей $g$ в соответствии с позицией, записанной в локальной конфигурации. Поскольку шаг $4$ — это чистое движение головки, а шаг $5$ вовсе не требует движения головки, эти два шага можно объединить в один шаг $M^{\prime }$.)

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

(В доказательстве теоремы 6.10 локальная конфигурация состоит из $3m$ ячеек ленты $M$, позиции головки в пределах этих $3m$ ячеек и состояния $M$ — то есть это строка $a_{1} \cdots a_{3 m} \in \Gamma^{3 m}$ вместе с отмеченной позицией $1 \leq i \leq 3 m$ и состоянием $q$ автомата $M$, где $\Gamma$ — алфавит ленты $M$.)

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

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

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