34.4 NP-completeness proofs

34.4-1

Consider the straightforward (nonpolynomial-time) reduction in the proof of Theorem 34.9. Describe a circuit of size $n$ that, when converted to a formula by this method, yields a formula whose size is exponential in $n$.

(Omit!)

34.4-2

Show the $\text{3-CNF}$ formula that results when we use the method of Theorem 34.10 on the formula $\text{(34.3)}$.

(Omit!)

34.4-3

Professor Jagger proposes to show that $\text{SAT} \le_\text P \text{3-CNF-SAT}$ by using only the truth-table technique in the proof of Theorem 34.10, and not the other steps. That is, the professor proposes to take the boolean formula $\phi$, form a truth table for its variables, derive from the truth table a formula in $\text{3-DNF}$ that is equivalent to $\neg\phi$, and then negate and apply DeMorgan's laws to produce a $\text{3-CNF}$ formula equivalent to $\phi$. Show that this strategy does not yield a polynomial-time reduction.

(Omit!)

34.4-4

Show that the problem of determining whether a boolean formula is a tautology is complete for $\text{co-NP}$. ($\textit{Hint:}$ See Exercise 34.3-7.)

(Omit!)

34.4-5

Show that the problem of determining the satisfiability of boolean formulas in disjunctive normal form is polynomial-time solvable.

(Omit!)

34.4-6

Suppose that someone gives you a polynomial-time algorithm to decide formula satisfiability. Describe how to use this algorithm to find satisfying assignments in polynomial time.

(Omit!)

34.4-7

Let $\text{2-CNF-SAT}$ be the set of satisfiable boolean formulas in $\text{CNF}$ with exactly $2$ literals per clause. Show that $\text{2-CNF-SAT} \in P$. Make your algorithm as efficient as possible. ($\textit{Hint:}$ Observe that $x \vee y$ is equivalent to $\neg x \to y$. Reduce $\text{2-CNF-SAT}$ to an efficiently solvable problem on a directed graph.)

(Omit!)