Банк задач по математике

Пример 6.22

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

?

Пример 6.30

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

?

Пример 6.32

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

?

Задача 6.4.1

(a)(b)

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

?

(a)

$L_{1}=\left\{ a^{i_{1}} b a^{i_{2}} b \cdots b a^{i_{k}} \mid i_{1}, i_{2}, \ldots , i_{k} \geq 0, k \geq 3, i_{r}=i_{s}=i_{t}\text{ для некоторых }1 \leq r<s<t \leq k\right\}$ .

(b)

$L_{2}=\left\{ x_{1} c x_{2} c \cdots c x_{m} c c y \mid x_{1}, \ldots , x_{m}, y \in \left\{ a, b\right\}^{*},\left(\exists i_{1}, \ldots , i_{k}\right)[1 \leq \left.i_{1}<\cdots <i_{k} \leq m, x_{i_{1}} x_{i_{2}} \cdots x_{i_{k}}=y\right]\right\}$ .

Задача 6.4.2

(a)(b)(c)

?

(a)

Регулярное выражение $r$ называется беззвёздным регулярным выражением, если оно не содержит символ * (звезду Клини). Покажите, что задача определения того, не эквивалентны ли два беззвёздных регулярных выражения $r_{1}$ и $r_{2}$ (то есть, верно ли $L\left(r_{1}\right) \neq L\left(r_{2}\right)$ ), принадлежит $N P$ .

(b)

Покажите, что задача определения того, не эквивалентны ли два регулярных выражения, принадлежит $\operatorname {NSPACE}(n)$ .

(c)

Расширенное регулярное выражение — это регулярное выражение, в котором может использоваться дополнительная операция пересечения (обозначаемая $\cap$ ). Покажите, что задача определения того, не эквивалентны ли два расширенных регулярных выражения, принадлежит $\bigcup_{c>0} \operatorname {NSPACE}\left(2^{c n}\right)$ .

Задача 6.4.3

В доказательстве теоремы 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)$ , что проверяется рекурсивным вызовом того же алгоритма для каждого из них.)

?

Задача 6.4.4

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

?

Задача 6.4.5

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

\operatorname {NSPACE}\left(n^{r}\right) \stackrel{\subset }{\neq } \operatorname {NSPACE}\left(n^{r+\epsilon }\right).

?

Задача 6.4.6

(a)(b)

?

(a)

Покажите, что лемма 6.31 по-прежнему верна, если заменить условия $s_{2}(n) \geq n$ и $f(n) \geq n$ на $s_{2}(n) \geq \log n$ и $\log (f(n))= O\left(s_{2}(n)\right)$ . [Подсказка: заметим, что НМТ $M_{3}$ может моделировать $M_{2}$ на входе $y=x S^{f(\left|x\right|)-\left|x\right|}$ , не выписывая строку $y$ на второй ленте. Вместо этого она может просто записывать на второй ленте позицию $k$ головки входной ленты $M_{2}$ и использовать $k$ , чтобы определить, какой входной символ сканирует головка ленты $M_{2}$ .]

(b)

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

\operatorname {NSPACE}\left(n^{r}\right) \stackrel{\subset }{\neq } \operatorname {NSPACE}\left(n^{r+\epsilon }\right).

Задача 6.4.7

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

?

Задача 6.4.8

(a)(b)

?

(a)

Покажите, что $E X P \neq N P$ .

(b)

Покажите, что EXP $\neq \bigcup_{c>0} \operatorname {DTIME}\left(2^{n^{c}}\right)$ .

Задача 6.4.9

Покажите, что если $P=N P$ , то

\bigcup _{c>0} \operatorname {DTIME}\left(2^{n^{c}}\right)=\bigcup _{c>0} \operatorname {NTIME}\left(2^{n^{c}}\right).

?

Недетерминированные машины Тьюринга