Problems

Let $\operatorname {EQ}_{\text{REX }}=\left\{ \langle R, S\rangle \mid R\text{ and }S\text{ are equivalent regular expressions }\right\}$. Show that $\operatorname {EQ}_{\text{REX }} \in$ PSPACE.

A ladder is a sequence of strings $s_{1}, s_{2}, \ldots , s_{k}$, wherein every string differs from the preceding one by exactly one character. For example, the following is a ladder of English words, starting with "head" and ending with "free": head, hear, near, fear, bear, beer, deer, deed, feed, feet, fret, free. Let $\operatorname {LADDER}_{\text{DFA }}=\left\{ \langle M, s, t\rangle \mid M\text{ is a DFA and }L(M)\text{ contains a ladder of strings, starting with }s\text{ and ending with }t\right\}$. Show that $\operatorname {LADDER}_{\text{DFA }}$ is in PSPACE.

The Japanese game go-moku is played by two players, "X" and "O," on a 19 × 19 grid. Players take turns placing markers, and the first player to achieve five of her markers consecutively in a row, column, or diagonal is the winner. Consider this game generalized to an $n \times n$ board. Let

By a position we mean a board with markers placed on it, such as may occur in the middle of a play of the game, together with an indication of which player moves next. Show that $\operatorname {GM} \in$ PSPACE.

Show that if every NP-hard language is also PSPACE-hard, then PSPACE = NP.

Show that $T Q B F$ restricted to formulas where the part following the quantifiers is in conjunctive normal form is still PSPACE-complete.

Define $A_{\text{LBA }}=\left\{ \langle M, w\rangle \mid M\text{ is an LBA that accepts input }w\right\}$. Show that $A_{\text{LBA }}$ is PSPACE-complete.

• The cat-and-mouse game is played by two players, "Cat" and "Mouse," on an arbitrary undirected graph. At a given point, each player occupies a node of the graph. The players take turns moving to a node adjacent to the one that they currently occupy. A special node of the graph is called "Hole." Cat wins if the two players ever occupy the same node. Mouse wins if it reaches the Hole before the preceding happens. The game is a draw if a situation repeats (i.e., the two players simultaneously occupy positions that they simultaneously occupied previously, and it is the same player's turn to move).

Show that HAPPY-CAT is in P. (Hint: The solution is not complicated and doesn't depend on subtle details in the way the game is defined. Consider the entire game tree. It is exponentially big, but you can search it in polynomial time.)

Consider the following two-person version of the language PUZZLE that was described in Problem 7.28. Each player starts with an ordered stack of puzzle cards. The players take turns placing the cards in order in the box and may choose which side faces up. Player I wins if all hole positions are blocked in the final stack, and Player II wins if some hole position remains unblocked. Show that the problem of determining which player has a winning strategy for a given starting configuration of the cards is PSPACE-complete.

Problem 7.28: You are given a box and a collection of cards, each of which fits in the box in either of two ways because of pegs in the box and notches in the cards. Each card contains two columns of holes, some of which may not be punched out. The puzzle is solved by placing all the cards in the box so as to completely cover the bottom of the box (i.e., every hole position is blocked by at least one card that has no hole there). $\operatorname {PUZZLE}=\left\{ \left\langle c_{1}, \ldots , c_{k}\right\rangle \mid \text{each } c_{i} \text{ represents a card and this collection of cards has a solution}\right\}$.

Read the definition of MIN-FORMULA in Problem 7.46.

Problem 7.46: Say that two Boolean formulas are equivalent if they have the same set of variables and are true on the same set of assignments to those variables (i.e., they describe the same Boolean function). A Boolean formula is minimal if no shorter Boolean formula is equivalent to it. MIN-FORMULA is the collection of minimal Boolean formulas.

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

• Let $B$ be the language of properly nested parentheses and brackets. For example, (()()[])is in $B$ but ([)] is not. Show that $B$ is in L.

• 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 1s 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.

Let $\operatorname {MULT}=\left\{ a \# b \# c \mid a, b, c\text{ are binary natural numbers and }a \times b=c\right\}$. Show that MULT $\in \mathrm{L}$.

For any positive integer $x$, let $x^{\mathcal{R}}$ be the integer whose binary representation is the reverse of the binary representation of $x$. (Assume no leading 0s in the binary representation of $x$.) Define the function $\mathcal{R}^{+}: \mathcal{N} \longrightarrow \mathcal{N}$ where $\mathcal{R}^{+}(x)=x+x^{\mathcal{R}}$.

• Define $\operatorname {UCYCLE}=\left\{ \langle G\rangle \mid G\text{ is an undirected graph that contains a simple cycle }\right\}$. Show that UCYCLE $\in \mathrm{L}$. (Note: $G$ may be a graph that is not connected.)

• For each $n$, exhibit two regular expressions, $R$ and $S$, of length $\operatorname {poly}(n)$, where $L(R) \neq L(S)$, but where the first string on which they differ is exponentially long. In other words, $L(R)$ and $L(S)$ must be different, yet agree on all strings of length up to $2^{\epsilon n}$ for some constant $\epsilon >0$.

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 BIPARTITE $=\left\{ \langle G\rangle \mid G\text{ is a bipartite graph }\right\}$. Show that BIPARTITE $\in$ NL.

Define UPATH to be the counterpart of PATH for undirected graphs. Show that $\overline{\text{ BIPARTITE }} \leq_{\mathrm{L}}$ UPATH. (Note: In fact, we can prove UPATH $\in \mathrm{L}$, and therefore BIPARTITE $\in \mathrm{L}$, but the algorithm [62] is too difficult to present here.)

Recall that a directed graph is strongly connected if every two nodes are connected by a directed path in each direction. Let

Show that STRONGLY-CONNECTED is NL-complete.

Let $\operatorname {BOTH}_{\text{NFA }}=\left\{ \left\langle M_{1}, M_{2}\right\rangle \mid M_{1} \text{ and } M_{2} \text{ are NFAs where } L\left(M_{1}\right) \cap L\left(M_{2}\right) \neq \emptyset \right\}$. Show that $\operatorname {BOTH}_{\text{nfa }}$ is NL-complete.

Show that $A_{\text{NFA }}$ is NL-complete.

Show that $E_{\text{DFA }}$ is NL-complete.

• Show that 2SAT is NL-complete.

Let $\operatorname {CNF}_{\mathrm{H} 1}=\left\{ \langle \phi \rangle \mid \phi \text{ is a satisfiable cnf-formula where each clause contains any number of positive literals and at most one negated literal. Furthermore, each negated literal has at most one occurrence in }\phi \right\}$. Show that $\operatorname {CNF}_{\mathrm{H} 1}$ is NLcomplete.

• Give an example of an NL-complete context-free language.

ᴬ Define $\operatorname {CYCLE}=\left\{ \langle G\rangle \mid G\text{ is a directed graph that contains a directed cycle }\right\}$. Show that CYCLE is NL-complete.