Задачи

Пусть $E Q_{\text{REX }}=\left\{ \langle R, S\rangle \mid R\text{ и }S\text{ — эквивалентные регулярные выражения}\right\}$. Покажите, что $E Q_{\text{REX }} \in$ PSPACE.

Лестницей называется последовательность строк $s_{1}, s_{2}, \ldots , s_{k}$, в которой каждая строка отличается от предыдущей ровно одним символом. Например, вот лестница из английских слов, начинающаяся с «head» и заканчивающаяся «free»: head, hear, near, fear, bear, beer, deer, deed, feed, feet, fret, free. Пусть $L A D D E R_{\text{DFA }}=\left\{ \langle M, s, t\rangle \mid M\text{ — ДКА, и }L(M)\text{ содержит лестницу строк, начинающуюся с }s\text{ и заканчивающуюся }t\right\}$. Покажите, что $L A D D E R_{\text{DFA }}$ принадлежит PSPACE.

В японской игре го-моку двое игроков, «X» и «O», играют на доске $19 \times 19$. Игроки по очереди ставят фишки, и выигрывает тот, кто первым выстроит пять своих фишек подряд по горизонтали, вертикали или диагонали. Рассмотрим эту игру, обобщённую на доску $n \times n$. Пусть

Под позицией мы понимаем доску с расставленными на ней фишками — такую, какая может встретиться в середине партии, — вместе с указанием того, чей ход следующий. Покажите, что $G M \in$ PSPACE.

Покажите, что если каждый NP-трудный язык также PSPACE-труден, то PSPACE = NP.

Покажите, что $T Q B F$, ограниченная формулами, где часть после кванторов записана в конъюнктивной нормальной форме, по-прежнему PSPACE-полна.

Определим $A_{\text{LBA }}=\left\{ \langle M, w\rangle \mid M\text{ — ЛОА, допускающий вход }w\right\}$. Покажите, что $A_{\text{LBA }}$ PSPACE-полна.

• Игра «кот и мышь» ведётся двумя игроками, «Кот» и «Мышь», на произвольном неориентированном графе. В каждый момент каждый игрок занимает некоторую вершину графа. Игроки по очереди перемещаются в вершину, смежную с той, которую они занимают в данный момент. Особая вершина графа называется «Нора». Кот выигрывает, если игроки когда-либо оказываются в одной и той же вершине. Мышь выигрывает, если она достигает Норы раньше, чем произойдёт предыдущее событие. Игра завершается вничью, если ситуация повторяется (то есть оба игрока одновременно занимают позиции, которые они уже одновременно занимали ранее, причём ход того же самого игрока).

Покажите, что HAPPY-CAT принадлежит P. (Подсказка: решение несложное и не зависит от тонких деталей того, как именно определена игра. Рассмотрите всё дерево игры целиком. Оно экспоненциально велико, но его можно обойти за полиномиальное время.)

Рассмотрим следующий вариант языка PUZZLE, описанного в задаче 7.28, для двух игроков. Каждый игрок начинает с упорядоченной стопкой карточек-головоломки. Игроки по очереди кладут карточки по порядку в коробку и могут выбирать, какой стороной вверх. Игрок I выигрывает, если в итоговой стопке все позиции отверстий перекрыты, а Игрок II выигрывает, если хотя бы одна позиция отверстия остаётся не перекрытой. Покажите, что задача определения того, у какого игрока есть выигрышная стратегия для данной начальной конфигурации карточек, PSPACE-полна.

Задача 7.28: Вам дана коробка и набор карточек, каждая из которых помещается в коробку одним из двух способов благодаря штырькам в коробке и выемкам на карточках. Каждая карточка содержит два столбца отверстий, некоторые из которых могут быть непробитыми. Головоломка решена, если все карточки размещены в коробке так, что полностью закрывают дно коробки (т.е. каждая позиция отверстия перекрыта хотя бы одной карточкой, у которой в этом месте нет отверстия). $\operatorname {PUZZLE}=\left\{ \left\langle c_{1}, \ldots , c_{k}\right\rangle \mid \text{каждая } c_{i} \text{ представляет карточку, и для этого набора карточек существует решение}\right\}$.

Вспомните определение MIN-FORMULA из задачи 7.46.

Пусть $A$ — язык правильно вложенных скобок. Например, (()) и (()(()))() принадлежат $A$, а )( — нет. Покажите, что $A$ принадлежит L.

• Пусть $B$ — язык правильно вложенных круглых и квадратных скобок. Например, (()()[]) принадлежит $B$, а ([)] — нет. Покажите, что $B$ принадлежит L.

• Игра Ним ведётся с набором кучек камней. За один ход игрок может убрать любое ненулевое число камней из одной кучки. Игроки по очереди делают ходы. Игрок, убирающий самый последний камень, проигрывает. Пусть у нас есть игровая позиция в Ниме с $k$ кучками, содержащими $s_{1}, \ldots , s_{k}$ камней. Назовём позицию сбалансированной, если в каждом разряде бит нечётное число единиц не встречается — то есть каждый разряд содержит чётное число единиц, — когда каждое из чисел $s_{i}$ записано в двоичной системе, а сами двоичные числа выписаны в виде строк матрицы, выровненных по младшим разрядам. Докажите следующие два факта.

Пусть $M U L T=\left\{ a \# b \# c \mid a, b, c\text{ — двоичные натуральные числа, и }a \times b=c\right\}$. Покажите, что MULT $\in \mathrm{L}$.

Для произвольного положительного целого $x$ пусть $x^{\mathcal{R}}$ — целое число, двоичная запись которого является обращением двоичной записи $x$. (Считайте, что в двоичной записи $x$ нет ведущих нулей.) Определим функцию $\mathcal{R}^{+}: \mathcal{N} \longrightarrow \mathcal{N}$, где $\mathcal{R}^{+}(x)=x+x^{\mathcal{R}}$.

• Определим $U C Y C L E=\left\{ \langle G\rangle \mid G\text{ — неориентированный граф, содержащий простой цикл}\right\}$. Покажите, что UCYCLE $\in \mathrm{L}$. (Примечание: $G$ может быть графом, не являющимся связным.)

• Для каждого $n$ предъявите два регулярных выражения, $R$ и $S$, длины $\operatorname {poly}(n)$, для которых $L(R) \neq L(S)$, но первая строка, на которой они различаются, имеет экспоненциальную длину. Иными словами, $L(R)$ и $L(S)$ должны быть различны, но при этом совпадать на всех строках длины вплоть до $2^{\epsilon n}$ для некоторой константы $\epsilon >0$.

Неориентированный граф называется двудольным, если его вершины можно разбить на два множества так, чтобы все рёбра шли из вершины одного множества в вершину другого. Покажите, что граф двудолен тогда и только тогда, когда он не содержит цикла с нечётным числом вершин. Пусть BIPARTITE $=\left\{ \langle G\rangle \mid G\text{ — двудольный граф}\right\}$. Покажите, что BIPARTITE $\in$ NL.

Определим UPATH как аналог PATH для неориентированных графов. Покажите, что $\overline{\text{ BIPARTITE }} \leq_{\mathrm{L}}$ UPATH. (Примечание: на самом деле можно доказать, что UPATH $\in \mathrm{L}$, а значит, и BIPARTITE $\in \mathrm{L}$, но алгоритм [62] слишком сложен, чтобы приводить его здесь.)

Вспомним, что ориентированный граф называется сильно связным, если любые две вершины соединены ориентированным путём в каждом направлении. Пусть

Покажите, что STRONGLY-CONNECTED NL-полна.

Пусть $\operatorname {BOTH}_{\text{NFA }}=\left\{ \left\langle M_{1}, M_{2}\right\rangle \mid M_{1} \text{ и } M_{2} \text{ — НКА, для которых } L\left(M_{1}\right) \cap L\left(M_{2}\right) \neq \emptyset \right\}$. Покажите, что $\operatorname {BOTH}_{\text{nfa }}$ NL-полна.

Покажите, что $A_{\text{NFA }}$ NL-полна.

Покажите, что $E_{\text{DFA }}$ NL-полна.

• Покажите, что 2SAT NL-полна.

Пусть $C N F_{\mathrm{H} 1}=\left\{ \langle \phi \rangle \mid \phi \text{ — выполнимая кнф-формула, в которой каждый дизъюнкт содержит произвольное число положительных литералов и не более одного отрицательного литерала. Более того, каждый отрицательный литерал встречается в }\phi \text{ не более одного раза}\right\}$. Покажите, что $C N F_{\mathrm{H} 1}$ NL-полна.

• Приведите пример NL-полного контекстно-свободного языка.

Определим $C Y C L E=\left\{ \langle G\rangle \mid G\text{ — ориентированный граф, содержащий ориентированный цикл}\right\}$. Покажите, что CYCLE NL-полна.