Вычислительная сложность

Пусть даны три стержня и $n$ дисков, причём все $n$ дисков имеют разный размер. Изначально $n$ дисков сложены в порядке убывания размера, снизу вверх, на первом стержне (см. рис. 6.1). Задача о Ханойской башне состоит в том, чтобы перенести всю башню из $n$ дисков с первого стержня на второй, перемещая по одному диску за раз и никогда не кладя больший диск на меньший. Каково самое быстрое решение этой задачи? Является ли самое быстрое решение практически осуществимым при размере $n=64$ (размере исходной задачи о Ханойской башне)?

Рис. 6.1: задача о Ханойской башне.

Покажите, что функция $2^{\sqrt{\log n}}$ растёт медленнее любой функции полиномиальной последовательности, но быстрее любой функции полилогарифмической последовательности.

Пусть $f(n) \prec g(n)$. Покажите, что существует функция $h(n)$, такая что $f(n) \prec h(n) \prec g(n)$.

Покажите, что $\log^{*} n \prec \log^{(m)} n$ для любого фиксированного целого $m \geq 1$.

Покажите, что $2^{\ln n}=o(n)$ и $2^{\log (2 n)}=O(n)$.

Покажите, что $(\log n)^{10} \prec n^{10} \prec 2^{(\log n)^{10}}$.

Сравните следующие три функции с помощью обозначения $\prec$:

Сравните $2^{\log { }^{*} n}$ и $n$ с помощью обозначения $\prec$.

Пусть $f(n) \prec g(n)$. Верно ли, что для любой возрастающей функции $h(n)$ с $\lim_{n \rightarrow \infty } h(n)=\infty$ выполняется $h(f(n)) \prec h(g(n))$? Приведите доказательство или контрпример.

Докажите, что $\log^{(k+1)} \prec \log^{(k)} n$ для любого $k \geq 0$.

Обозначим $\log^{* *} n=\min \left\{ k \mid \left(\log^{*}\right)^{(k)} n \leq 1, k \geq 1\right\}$. Сравните $\log^{* *} n$ и $\log^{*} n$.

Вспомните функцию Аккермана $A$, определённую в упражнении 8 раздела 4.8.

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

Покажите, что $(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)$.

Пусть $L=\left\{ a^{i_{1}} b a^{i_{2}} b \cdots b a^{i_{k}} b b a^{j} \mid i_{1}, \ldots , i_{k}, j>0, \sum_{r \in A} i_{r}=j\text{ для некоторого }A \subseteq \left\{ 1,2, \ldots , k\right\} \right\}$. Постройте НМТ, допускающую язык $L$.

Покажите, что $\operatorname {NSPACE}(n) \underset {\neq }{\subseteq } \operatorname {NSPACE}(n^{2} \log n)$.

Покажите, что NSPACE $(n) \underset {\neq }{\subseteq } N \operatorname {SPACE}\left(n^{1.5}\right)$.

Постройте многоленточные НМТ, допускающие следующие языки за время $t(n)=2 n$:

В доказательстве теоремы 6.27 предикат $\operatorname {reach}\left(\alpha_{1}, \alpha_{2}, 2^{i}\right)$ решался детерминированным рекурсивным алгоритмом. Преобразуйте его в эквивалентный нерекурсивный алгоритм, использующий память $O\left((s(n))^{2}\right)$.

Покажите, что класс сложности NP замкнут относительно объединения, пересечения, конкатенации и замыкания Клини.

Покажите, что для любых вещественных чисел $r \geq 1$ и $0<\epsilon <1$,

Покажите, что если $t_{1}(n), t_{2}(n)$ и $f(n)$ — вполне временно-конструируемые функции с $t_{2}(n) \geq n$ и $f(n) \geq n$, то $\operatorname {NTIME}\left(t_{1}(n)\right) \subseteq \operatorname {NTIME}\left(t_{2}(n)\right)$ влечёт $\operatorname {NTIME}\left(t_{1}(f(n))\right) \subseteq \operatorname {NTIME}\left(t_{2}(f(n))\right)$.

Покажите, что если $P=\mathrm{NP}$, то

Найдите контекстно-зависимую грамматику для языка

Найдите контекстно-зависимую грамматику для языка

Постройте контекстно-зависимые грамматики для языков из примеров 4.17 и 4.18, а также для языков из упражнений 3(b)-3(i) раздела 4.5.

Завершите последнюю часть доказательства теоремы 6.35. То есть опишите, как присоединить самый левый и самый правый пробелы к соседним символам, чтобы преобразовать грамматику $G_{2}$ в контекстно-зависимую грамматику.

Покажите, что класс контекстно-зависимых языков замкнут относительно объединения, пересечения, конкатенации и замыкания Клини.

Найдите рекурсивный язык $L$, не являющийся контекстно-зависимым.

Что не так, если для вычисления $N_{k}$ в доказательстве теоремы 6.36 использовать следующий более простой алгоритм?

Для каждого $k$, чтобы вычислить $N_{k}$, мы порождаем каждую конфигурацию $\alpha \in C_{x}$ одну за другой и для каждой недетерминированно проверяем, выполнено ли $\operatorname {reach}(\beta , \alpha , k)$ (машиной $M_{1}$), и увеличиваем счётчик для $N_{k}$ на единицу, если $\operatorname {reach}(\beta , \alpha , k)$ выполнено.

Вспомним, из упражнения 6 раздела 3.5, понятие 2-стекового PDA. Покажите, что каждый язык, допускаемый 2-стековым PDA, является контекстно-зависимым языком.