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

Пусть даны три стержня и $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, 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$.

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

Пусть $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)$.

($\operatorname {reach}\left(\alpha_{1}, \alpha_{2}, k\right)$ обозначает предикат, что $M$ может перейти от конфигурации $\alpha_{1}$ к конфигурации $\alpha_{2}$ не более чем за $k$ ходов. Доказательство теоремы 6.27 определяет $\operatorname {reach}\left(\alpha_{1}, \alpha_{2}, 2^{i}\right)$ рекурсивно: если $i=0$, оно возвращает ДА тогда и только тогда, когда $\alpha_{1} \vdash \alpha_{2}$ или $\alpha_{1}=\alpha_{2}$; если $i \geq 1$, оно возвращает ДА тогда и только тогда, когда для некоторой конфигурации $\alpha_{3}$ выполнены оба предиката $\operatorname {reach}\left(\alpha_{1}, \alpha_{3}, 2^{i-1}\right)$ и $\operatorname {reach}\left(\alpha_{3}, \alpha_{2}, 2^{i-1}\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=N P$, то

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

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

Постройте контекстно-зависимые грамматики для языков из примеров 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)$ выполнено.

($C_{x}$ обозначает множество конфигураций $M$ на входе $x$ длины $\leq s(n)$, $M_{1}$ — это НМТ, допускающая $\operatorname {reach}(\alpha , \beta , k)$ с памятью $O(s(n)+\log k)$ для $\alpha , \beta \in C_{x}$, а $N_{k}$ обозначает число конфигураций в $C_{x}$, достижимых из фиксированной конфигурации $\beta$ не более чем за $k$ ходов. Алгоритм, реально используемый в доказательстве для вычисления $N_{k+1}$ из $N_{k}$: для каждой $\alpha \in C_{x}$ угадать, в возрастающем порядке относительно фиксированного линейного порядка $\prec$ на $C_{x}$, конфигурации $\gamma_{1} \prec \cdots \prec \gamma_{N_{k}}$, достижимые из $\beta$ за $k$ ходов (каждая проверяется через $M_{1}$), затем установить $r_{\alpha }$ в ИСТИНА, если $\operatorname {reach}(\gamma_{i}, \alpha , 1)$ выполнено для некоторого $i$ — это одно прямо проверяемое условие достижимости за один ход, не требующее дальнейшего угадывания, — и увеличить $N_{k+1}$, если $r_{\alpha }=$ ИСТИНА.)

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