Упражнения

Покажите, что для любой функции $f: \mathcal{N} \longrightarrow \mathcal{R}^{+}$, где $f(n) \geq n$, класс ёмкостной сложности $\operatorname {SPACE}(f(n))$ один и тот же, определяем ли мы его с помощью модели однoленточной МТ или модели двухленточной МТ с входной лентой только для чтения.

Рассмотрим следующую позицию в стандартной игре в крестики-нолики.

Предположим, что следующий ход делает игрок ×. Опишите выигрышную стратегию для этого игрока. (Напомним, что выигрышная стратегия — это не просто наилучший ход в текущей позиции. Она также включает все ответные ходы, которые этот игрок должен сделать, чтобы выиграть, как бы ни ходил противник.)

Рассмотрим следующую обобщённую игру в географию, в которой начальной является вершина, в которую входит стрелка ниоткуда. Есть ли у Игрока I выигрышная стратегия? А у Игрока II? Обоснуйте свои ответы.

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

Покажите, что $A_{\text{DFA }} \in \mathrm{L}$.

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

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