In normal 3-SAT, a satisfying assignment of variables is an assignment where eac

Question

In normal 3-SAT, a satisfying assignment of variables is an assignment where each clause has at least one of its variables satisfied. So in a satisfying assignment of an instance of 3-SAT, each clause is satisfied by 1, 2, or 3 of its variables. Consider the problem PARTIAL SAT, which is like 3-SAT, except clauses are not allowed to have all of their variables satisfied - they must all be satisfied by 1 or 2 of their variables.

For example, consider (x1 x2 ¬x3) (¬x1 x2 ¬x3). If we take that as an instance of 3-SAT, setting x1 and x3 to false, and x2 to true, would satisfy it. However, that would not be a valid solution to the instance of PARTIAL SAT, since all 3 variables in the second clause are satisfied by that truth assignment. Setting x1 and x2 to true, and x3 to false, however, would solve the instance of PARTIAL SAT, since the first clause is satisfied by 2 variables and the second clause is satisfied by 1 variable.

Prove that PARTIAL SAT is NP-complete. (Hint: reduce from 3-SAT; for each clause in the original instance of 3-SAT, make 2 clauses in PARTIAL SAT using some new variables)

Explanation / Answer

A Boolean formula that is an AND of clauses, each of which is an OR of exactly 3 distinct literals.

3-CNF-SAT = { <>: is a satisfiable 3-CNF

            It is obvious that

            Now we need to construct the reduction algorithm

Step 1: Construct a binary parse tree for the input formula, with literals as leaves and connectives as internal nodes.

Step 2: Just as we did in pervious theorem, assign a variable for each output of internal node. Thus, the original formula can be rewritten as the AND of the root variable and a conjunction of clauses describing the operation of each node.

Now each clause has at most 3 variables but is not in disjunctive normal form.

For each clause i , identify all possible truth assignments that evaluate it to 0.

Using these assignments, we build a formula in disjunctive normal form that is equivalent to .

The CNF ofi can be converted by applying DeMorgan’s law. See p.944 for an example.

Step 3: We need to convert each clause Ci with less than 3 literals to that with exactly 3 literals.

            Case 1. If Ci has 2 literals, say we can convert it to

            Case 2. If Ci has 1 literal, say l, we can convert it to

The resulting formula after this conversion is satisfiable iffis satisfiable.

Step 1: It introduces at most 1 variable and 1 clause per connective in.

Step 2: Constructing from introduces at most 8 clauses into for each clause in .

Step 3: Constructing from introduces at most 4 clauses for each clause of

            The brute-force algorithm takes

            The verification algorithm takes G and a subset V’ of V vertices as the certificate. It checks whether V’ is a clique in polynomial time by checking whether, for each pair the edge

            Letbe a Boolean formula in 3-CNF with k clauses, where .

            For each clause Cr, place a triple of vertices V1r, V2r, V3r.

Regarding edges, 2 vertices iff

2. lir and ljs are consistent, i.e. lir is not the negation of ljs.

            This graph can be computed in polynomial time (why?)

1.Supposehas a satisfying assignment. Therefore, each clauses Ci contains at least one literal lir that is assigned 1. Besides, any pair of such literals must be consistent. Therefore, pick one such literal from each clause yields a set of V’ of k vertices and V’ must be a clique.

2.Suppose G has a clique V’ of size k. V’ contains exactly one vertex per triple. Assigning 1 to each literal lir s.t. yields a satisfying assignment.

. A vertex cover of G=(V, E) is a subset V’ of V s.t. if then either

Optimization problem: Find a vertex cover of minimum size.

Decision problem: Determine if there exists a vertex cover of size k.

Proof.

1.

                        The verification algorithm takes G=(V, E) as the input and a subset V’ of V of vertices as the certificate. It checks if and if every edge , whether The execution time is polynomial.

Let V’ be a clique of size k in G. Then for every hat is, V-V’ is a vertex cover of

            Let V’ be a vertex cover of , then for every

            In other words, V-V’ is a clique of G.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.