Consider the straightforward (nonpolynomial-time) reduction in the proof of Theo
ID: 3868825 • Letter: C
Question
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. Satisfiability of boolean formulas is NP-complete. Proof We start by arguing that SAT element NP. Then we prove that CIRCUIT-SAT is NP-hard by showing that CIRCUIT-SAT lessthanorequalto p SAT: by Lemma 34.8.this will prove the theorem. To show that SAT belongs to NP.we show that a certificate consisting of a satisfying assignment for an input formula phi can be verified in polynomial time. The verifying algorithm simply replaces each variable in the formula with its corresponding value and then evaluates th expression. much as we did in equation (34.2) above. This task is easily done in polynomial time. If the expression evaluates to 1.the formula is satisfiable. Thus.the first condition of Lemma 34.8 for NP-completeness holds. To prove that SAT is NP-hard.we shExplanation / Answer
Many problems can be proved NP-complete by reduction from formula satisfiability. The reduction algorithm must handle any input formula, though, and this requirement can lead to a huge number of cases that must be considered. It is often desirable, therefore, to reduce from a restricted language of boolean formulas, so that fewer cases need be considered. Of course, we must not restrict the language so much that it becomes polynomial-time solvable. One convenient language is 3-CNF satisfiability, or 3-CNF-SAT. We define 3-CNF satisfiability using the following terms. A literal in a boolean formula is an occurrence of a variable or its negation. A boolean formula is in
For example, the boolean formula (x1 x1 x2 x3 x2 x4 x1 x3 x4) is in 3-CNF. The first of its three clauses is (x1 x1 x2), which contains the three literals x1, x1, and x2. In 3-CNF-SAT, we are asked whether a given boolean formula in 3-CNF is satisfiable. The following theorem shows that a polynomial-time algorithm that can determine the satisfiability of boolean formulas is unlikely to exist, even when they are expressed in this simple normal form. conjunctive normal form, or CNF, if it is expressed as an AND of clauses, each of which is the OR of one or more literals. A boolean formula is in 3-conjunctive normal form,