Chapter 8: Chapter 8

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} .\)

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.)

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 \(C N F_{\mathrm{H} 1}=\\{\langle\phi\rangle \mid \phi\) 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\\}\). Show that \(C N F_{\mathrm{H} 1}\) is NLcomplete.

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

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

Let \(E Q_{\mathrm{REX}}=\\{\langle R, S\rangle \mid R\) and \(S\) are equivalent regular expressions \(\\} .\) Show that \(E Q_{\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 \(L A D D E R_{\mathrm{DFA}}=\\{\langle M, s, t\rangle \mid M\) is a DFA and \(L(M)\) contains a ladder of strings, starting with \(s\) and ending with \(t\\}\). Show that \(L A D D E R_{D F A}\) is in PSPACE.