91Ó°ÊÓ

For a cnf-formula $\mathbf{âˆ\dots }$ with $\mathit{m}$ variables and $\mathit{c}$clauses $\mathit{O}\left(cm\right)$ , show that you can construct in polynomial time an NFA with states that accept all nonsatisfying assignments, represented as Boolean strings of length $\mathit{m}$. Conclude that $\mathbf{\text{±Ê≲ӱÊ}}$ implies that NFAs cannot be minimized in polynomial time.

A 2cnf-formula is an AND of clauses, where each clause is an OR of at most two literals. Let . Show that. Show that $\mathbf{2}\mathit{S}\mathit{A}\mathit{T}\mathbf{∈}\mathit{P}$.

Modify the algorithm for context-free language recognition in the proof of Theorem 7.16 to give a polynomial time algorithm that produces a parse tree for a string, given the string and a CFG, if that grammar generates the string.

Say that two Boolean formulas are equivalentif 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 minimalif no shorter Boolean formula is equivalent to it. Let MIN-FORMULAbe the collection of minimal Boolean formulas. Show that if P = NP,$\mathit{M}\mathit{I}\mathit{N}\mathbf{-}\mathit{F}\mathit{O}\mathit{R}\mathit{M}\mathit{U}\mathit{L}\mathit{A}\mathbf{∈}\mathit{P}$

The difference hierarchy${\mathit{D}}_{\mathbf{i}}\mathit{P}$is defined recursively as

1. role="math" localid="1664206013824" ${\mathit{D}}_{\mathbf{1}}\mathit{P}\mathbf{∈}\mathit{N}\mathit{P}$and
2. ${\mathit{D}}_{\mathbf{i}}\mathit{P}\mathbf{=}\left\{A|A=B\backslash CforBinNPandCin{D}_{i-1}P\right\}\mathbf{.}$

(Here $\raisebox{1ex}{$\mathbf{B}$}\!\left/ \!\raisebox{-1ex}{$\mathbf{C}$}\right.\mathbf{=}\mathit{B}\mathbf{âˆ\copyright }\overline{\mathbf{C}}$.) For example, a language in D2P is the difference of two NP languages. Sometimes ${\mathit{D}}_{\mathbf{2}}\mathit{P}$ is called DP (and may be written DP). Let $\mathit{Z}\mathbf{=}\left\{(G_1,k_1,G_2,k_2)|G_{1}hasa{k}_1-cliqueand{G}_{2}doesn\text{'}thavea{k}_2-clique\right\}$

.Show that Z is complete for DP. In other words, show that Z is in DP and every language in DP is polynomial time reducible to Z.

Fill out the table described in the polynomial time algorithm for context-free language recognition from $\mathbf{Theorem}\mathbf{7}.\mathbf{16}\mathbf{for}\mathbf{string}\mathbf{w}=\mathbf{baba}\mathbf{and}\mathbf{CFG}\mathbf{G}:$

$$\begin{gathered} \mathbf{S}→\mathbf{RT} \\ \mathbf{R}\mathbf{→}\mathbf{T}\mathbf{R}\mathbf{|}\mathbf{a} \\ \mathbf{T}\mathbf{→}\mathbf{T}\mathbf{R}\mathbf{|}\mathbf{b} \end{gathered}$$

Call a regular expression star-freeif it does not contain any star operations.Then,let

$E{Q}_{\mathrm{SF}-\mathrm{REX}}=\left\{(\mathrm{R},\mathrm{S})|\mathrm{R}\mathrm{and}\mathrm{S}\mathrm{are}\mathrm{equivalent}\mathrm{star}-\mathrm{free}\mathrm{regular}\mathrm{expressions}\right\}$. Show that$E{Q}_{\mathbf{SF}-\mathbf{REX}}$ is in coNP. Why does your argument fail for general regular expressions?

This problem investigates resolution, a method for proving the unsatisfiability of cnf-formulas. Let $\mathrm{Ï•}=C_1âˆ\S C_2âˆ\S …âˆ\S C_m$be a formula in cnf, where the $C_i$are its clauses. Let $C=\left\{C_i\left|C_i \mathrm{is} \mathrm{a} \mathrm{clause} \mathrm{of} \mathrm{Ï•}\right.\right\}$. In a resolution step, we take two clauses $C_a$and $C_b$in C, which both have some variable occurring positively in one of the clauses and negatively in the other. Thus, $C_a=\left(x∨y_1∨y_2∨…∨y_k\right)$and $C_b=\left(\stackrel{¯}{x}∨z_1∨z_2∨…∨z_l\right)$, where the and are literals. We form the new clause $\left(y_1∨y_2∨…∨y_k∨z_1∨z_2∨…∨z_l\right)$and remove repeated literals. Add this new clause to C. Repeat the resolution steps until no additional clauses can be obtained. If the empty clause ( ) is in C, then declare $\mathrm{Ï•}$unsatisfiable. Say that resolution is sound if it never declares satisfiable formulas to be unsatisfiable. Say that resolution is complete if all unsatisfiable formulas are declared to be unsatisfiable.

a. Show that resolution is sound and complete.

b. Use part (a) to show that $2SAT∈P$.

Let $A⊆1^{*}$ be any unary language. Show that if A is NP-complete, then P = NP. (Hint: Consider a polynomial time reduction f from SATto A. For a formula $\mathrm{ϕ}$, let ${\mathrm{ϕ}}_{0100}$be the reduced formula where variables x1, x2, x3, and x4 in$\mathrm{ϕ}$ 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?)