Chapter 7: Chapter 7

Show that if \(\mathrm{P}=\mathrm{NP}\), a polynomial time algorithm exists that produces a satisfying assignment when given a satisfiable Boolean formula. (Note: The algorithm you are asked to provide computes a function; but NP contains languages, not functions. The \(\mathrm{P}=\mathrm{NP}\) assumption implies that \(S A T\) is in \(\mathrm{P}\), so testing satisfiability is solvable in polynomial time. But the assumption doesn't say how this test is done, and the test may not reveal satisfying assignments. You must show that you can find them anyway. Hint: Use the satisfiability tester repeatedly to find the assignment bit-by-bit.)

Fill out the table described in the polynomial time algorithm for context-free language recognition from Theorem \(7.16\) for string \(w=\) baba and CFG \(G\) : $$ \begin{aligned} &S \rightarrow R T \\ &R \rightarrow T R \mid \mathrm{a} \\ &T \rightarrow T R \mid \mathrm{b} \end{aligned} $$

Consider the algorithm MINIMIZE, which takes a DFA \(M\) as input and outputs \(\mathrm{DFA} M^{\prime} .\) MINIMIZE \(=\) "On input \(\langle M\rangle\), where $M=\left(Q, \Sigma, \delta, q_{0}, A\right)$ is a DFA: 1\. Remove all states of \(M\) that are unreachable from the start state. 2\. Construct the following undirected graph \(G\) whose nodes are the states of \(M\). 3\. Place an edge in \(G\) connecting every accept state with every nonaccept state. Add additional edges as follows. 4\. Repeat until no new edges are added to \(G\) : 5\. For every pair of distinct states \(q\) and \(r\) of \(M\) and every $a \in \Sigma$ : 6\. Add the edge \((q, r)\) to \(G\) if \((\delta(q, a), \delta(r, a))\) is an edge of \(G\). 7\. For each state \(q\), let \([q]\) be the collection of states \([q]=\\{r \in Q \mid\) no edge joins \(q\) and \(r\) in \(G\\} .\) 8\. Form a new DFA $M^{\prime}=\left(Q^{\prime}, \Sigma, \delta^{\prime}, q_{0}^{\prime}, A^{\prime}\right)$ where \(Q^{\prime}=\\{[q] \mid q \in Q\\}\) (if \([q]=[r]\), only one of them is in \(Q^{\prime}\) ), \(\delta^{\prime}([q], a)=[\delta(q, a)]\) for every \(q \in Q\) and $a \in \Sigma$, \(q_{0}^{\prime}=\left[q_{0}\right]\), and \(A^{\prime}=\\{[q] \mid q \in A\\} .\) 9\. Output \(\left\langle M^{\prime}\right\rangle . "\) a. Show that \(M\) and \(M^{\prime}\) are equivalent. b. Show that \(M^{\prime}\) is minimal-that is, no DFA with fewer states recognizes the same language. You may use the result of Problem \(1.52\) without proof. c. Show that MINIMIZE operates in polynomial time.

For a cnf-formula \(\phi\) with \(m\) variables and \(c\) clauses, show that you can construct in polynomial time an NFA with \(O(\mathrm{~cm})\) states that accepts all nonsatisfying assignments, represented as Boolean strings of length \(m\). Conclude that \(\mathrm{P} \neq \mathrm{NP}\) implies that NFAs cannot be minimized in polynomial time.

A \(2 c n f-\) formula is an AND of clauses, where each clause is an OR of at most two literals. Let \(2 S A T=\\{\langle\phi\rangle \mid \phi\) is a satisfiable \(2 \mathrm{cnf}\)-formula \(\\} .\) Show that $2 S A T \in \mathrm{P} .$

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. Let MIN-FORMULA be the collection of minimal Boolean formulas. Show that if \(\mathrm{P}=\mathrm{NP}\), then \(M I N-F O R M U L A \in \mathrm{P}\).

Is the following formula satisfiable? $$ (x \vee y) \wedge(x \vee \bar{y}) \wedge(\bar{x} \vee y) \wedge(\bar{x} \vee \bar{y}) $$

Call a regular expression star-free if it does not contain any star operations. Then, let $E Q_{\mathrm{SF}-\mathrm{REX}}=\\{\langle R, S\rangle \mid R\( and \)S\( are equivalent star-free regular expressions \)\\}$. Show that \(E Q_{\mathrm{SF}-\mathrm{REX}}\) is in coNP. Why does your argument fail for general regular expressions?

Call a regular expression star-free if it does not contain any star operations. Then, let $E Q_{\mathrm{SF}-\mathrm{REX}}=\\{\langle R, S\rangle \mid R\( and \)S\( are equivalent star-free regular expressions \)\\}$. Show that \(E Q_{\mathrm{SF}-\mathrm{REX}}\) is in coNP. Why does your argument fail for general regular expressions?

Let \(A \subseteq 1^{*}\) be any unary language. Show that if \(A\) is NP- complete, then \(\mathrm{P}=\mathrm{NP}\). (Hint: Consider a polynomial time reduction \(f\) from \(S A T\) to \(A\). For a formula \(\phi\), let \(\phi_{0100}\) be the reduced formula where variables \(x_{1}, x_{2}, x_{3}\), and \(x_{4}\) in \(\phi\) are set to the values \(0,1,0\), and 0 , respectively. What happens when you apply \(f\) to all of these exponentially many reduced formulas?)