Exercises

Show that for any function $f: \mathcal{N} \longrightarrow \mathcal{R}^{+}$, where $f(n) \geq n$, the space complexity class $\operatorname {SPACE}(f(n))$ is the same whether you define the class by using the singletape TM model or the two-tape read-only input TM model.

Consider the following position in the standard tic-tac-toe game.

Let's say that it is the ×-player's turn to move next. Describe a winning strategy for this player. (Recall that a winning strategy isn't merely the best move to make in the current position. It also includes all the responses that this player must make in order to win, however the opponent moves.)

Consider the following generalized geography game wherein the start node is the one with the arrow pointing in from nowhere. Does Player I have a winning strategy? Does Player II? Give reasons for your answers.

Show that PSPACE is closed under the operations union, complementation, and star.

ᴬ Show that $A_{\text{DFA }} \in \mathrm{L}$.

Show that any PSPACE-hard language is also NP-hard.

ᴬ Show that NL is closed under the operations union, concatenation, and star.