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

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用