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.

Let $B O T H_{\mathrm{NFA}}=\left\\{\left\langle M_{1}, M_{2}\right\rangle \mid M_{1}\right.\( and \)M_{2}\( are NFAs where \)\left.L\left(M_{1}\right) \cap L\left(M_{2}\right) \neq \emptyset\right\\} .\( Show that \)B O T H_{\mathrm{NFA}}$ is NL-complete.

Let \(A\) be the language of properly nested parentheses. For example, \((())\) and \((()(()))()\) are in \(A\), but ) ( is not. Show that \(A\) is in \(\mathrm{L}\).

An undirected graph is bipartite if its nodes may be divided into two sets so that all edges go from a node in one set to a node in the other set. Show that a graph is bipartite if and only if it doesn't contain a cycle that has an odd number of nodes. Let \(B I P A R T I T E=\\{\langle G\rangle \mid G\) is a bipartite graph \(\\} .\) Show that \(B I P A R T I T E \in \mathrm{NL} .\)

The game of Nim is played with a collection of piles of sticks. In one move, a player may remove any nonzero number of sticks from a single pile. The players alternately take turns making moves. The player who removes the very last stick loses. Say that we have a game position in Nim with \(k\) piles containing \(s_{1}, \ldots, s_{k}\) sticks. Call the position balanced if each column of bits contains an even number of \(1 \mathrm{~s}\) when each of the numbers \(s_{i}\) is written in binary, and the binary numbers are written as rows of a matrix aligned at the low order bits. Prove the following two facts. a. Starting in an unbalanced position, a single move exists that changes the position into a balanced one. b. Starting in a balanced position, every single move changes the position into an unbalanced one. Let \(N I M=\left\\{\left\langle s_{1}, \ldots, s_{k}\right\rangle \mid\right.\) each \(s_{i}\) is a binary number and Player I has a winning strategy in the Nim game starting at this position \(\\} .\) Use the preceding facts about balanced positions to show that \(N I M \in \mathrm{L}\).

Define \(U P A T H\) to be the counterpart of \(P A T H\) for undirected graphs. Show that \(\overline{B I P A R T I T E} \leq_{\mathrm{L}} U P A T H .\) (Note: In fact, we can prove \(U P A T H \in \mathrm{L}\), and therefore $B I P A R T I T E \in \mathrm{L}$, but the algorithm [62] is too difficult to present here.)