CS 21 Decidability and Tractability Winter 2024
Posted: February 21
Solution Set 5
If you have not yet turned in the Problem Set, you should not consult these solutions.
Copyright By PowCoder代写 加微信 powcoder
1. (a) We will reduce 2-COLORABLE to 2-SAT, which we showed to be in P. Given a graph G, our reduction produces the following set of clauses: label the vertices of G with variables x1, x2, . . . , xn; for every edge between vertices labelled xi and xj , produce the clauses (xi ∨ xj) and (xi ∨ xj).
Clearly this reduction runs in polynomial time. We now argue that “yes maps to yes.” If G is 2-colorable, then pick one of the two colors in a 2-coloring of G and assign the associated variables TRUE. Every one of the clauses is satisfied, because the only way to fail to satisfy a clause is if the two endpoints of some edges were the same color.
We argue that “no maps to no.” Suppose we have a satisfying assignment to the set of clauses produced by the reduction. Then the two variables associated with a given edge must have different truth assignments. Therefore, if we color the vertices of G associated with TRUE variables red, and the other vertices of G green, we will have produced a valid 2-coloring of G, and hence G is 2-colorable.
(b) First, note that 3-colorable is in NP because given an assignment of colors to the vertices of the graph G, we can verify in polynomial time that each edge has different colors at its endpoints.
To show that 3-colorable is NP-hard, we reduce from 3SAT. Given an instance φ of 3SAT, our reduction produces the following graph G: we have three special vertices A, B, C, and one vertex for each literal, xi and ¬xi. We have a triangle on A, xi, ¬xi for each i. Notice that any 3-coloring of the graph so far must assign distinct colors to B and C, which we will call (suggestively) T and F, respectively. Also each pair xi and ¬xi must be colored with T and F, respectively, or F and T, respectively. We can thus think of the coloring of the “literal vertices” as a truth assignment.
Now, for each clause (l1 ∨ l2 ∨ l3) appearing in φ, we add a copy of the gadget from the problem set. We identify the three grey vertices on the left with the three vertices l1, l2, and l3. We identify the grey vertex on the right with the vertex B. This reduction runs in polynomial time.
If we started with a YES instance of 3SAT, then we claim that the reduction produces a YES instance of 3-colorable. Consider a satisfying assignment for φ. We color A,B, and C with the colors RED, T and F , respectively. We then color xi and ¬xi with colors T and F, respectively, if xi is true in the satisfying assignment, and we color xi and ¬xi with colors F and T, respectively, if xi is false in the satisfying assignment. So far this is a valid 3-coloring. Now notice that every one of the clause gadgets has among its left three grey nodes at least one node that is colored T (since every clause has at least one true literal in the satisfying assignment). Moreover, its right grey node is colored
T. Thus using the observation in the problem set we can extend the 3-coloring to a 3-coloring of the clause gadgets, obtaining a 3-coloring of the entire graph G.
Now, if G is a YES instance of 3-colorable, then we claim that the reduction started with a satisfiable formula φ. Suppose we have a 3-coloring of G, then A, B, and C must be colored with three distinct colors, and let us call the color assigned to B “T” and the color assigned to C “F”. As noted each pair xi and ¬xi must be colored with T and F respectively, or F and T respectively. For each clause gadget, the rightmost grey node is colored with T, and so by the observation in the problem set, the only way it can be 3-colored is if at least one of its leftmost grey nodes are colored with T. But this means that we can set xi to true if it is colored T and xi to false if it is colored F, and the resulting assignment must satisfy every clause. Thus the formula φ is satisfiable, as required.
2. (3, 3)-sat is in NP for the same reason 3-SAT is. We show that it is NP-hard by reducing from 3-SAT.
Given a 3-CNF formula φ, we perform the following transformation to obtain 3-CNF φ′: for each xi we replace the mi occurrences of xi with fresh variables yi,1,yi,2,…,yi,mi, and we add the following mi clauses:
(¬yi,1 ∨ yi,2) (¬yi,2 ∨ yi,3) (¬yi,3 ∨ yi,4)
··· (¬yi,mi−1 ∨yi,mi) (¬yi,mi ∨ yi,1)
Note that the extra clauses are logically equivalent to:
yi,1⇒yi,2⇒…⇒yi,mi ⇒yi,1
and hence any assignment satisfying φ′ must set all of these variables to the same value. Such an assignment can be turned into a satisfying assignment for φ by setting xi = yi,1 for all i. Similarly, any assignment satisfying φ can be turned into a satisfying assignment for φ′ by setting yi,j = xi for all i,j. This shows that “yes maps to yes” and “no maps to no,” and thus (3, 3)-sat is NP-hard as required.
3. We first prove the following lemma regarding the 10 clauses given on the problem set: any assignment to x, y, z that sets at least one to true can be extended to an assignment to x, y, z, w that satisfies at most 7 of the 10 clauses, while the assignment to x, y, z that sets all of them to false cannot be extended to an assignment to x,y,z,w that satisfy more than 6 of the 10 clauses. Moreover it is impossible to satisfy more than 7 of the 10 clauses simultaneously.
The second part is easier: if x, y, z are all false, then setting w to true satisfies 4 clauses, while setting w to false satisfies 6 clauses. For the first part, observe that the clauses are symmetric in x, y, z. Thus we need only consider 3 cases: (a) exactly one of x, y, z is true, (b) exactly 2
of x,y,z are true, and (c) exactly 3 of x,y,z are true. In case (a), we can set w to false to satisfy 1 clause in the first row, 3 in the second row, and 3 in the last row, for a total of 7. In case (b), we can set w to true to satisfy 3 clauses in the first row, 2 in the second row, and 2 in the last row, for a total of 7. In case (c) we can set w to be true to satisfy 4 clauses in the first row, no clauses in the second row, and 3 clauses in the last row, for a total of 7. In each of these three cases, we see that setting w the other way doesn’t help: in case (a) we would satisfy only 6 clauses; in case (b) we would satisfy 7 clauses; in case (c) we would satisfy only 6 clauses. This proves the “moreover” part of the lemma.
Now we proceed with proving max2sat is NP-complete. Observe that it is in NP, because given a formula φ and an integer k, together with an assignment A, it is easy to verify in polynomial time that the assignment satisfies at least k of the clauses of φ.
Now, we show max2sat is NP-hard by reducing from 3SAT. Given an instance φ of 3SAT with m clauses, we produce a 2-CNF formula φ′ by replacing each clause (l1 ∨l2 ∨l3) with the 10 clauses in the problem set, with l1, l2, l3 in place of x, y, z. We use a fresh variable w for each clause of φ. The reduction sets the bound k = 7m. This reduction runs in polynomial time (it produces a 2-CNF φ′ with 10m clauses).
Suppose φ is satisfiable by an assignment A. Then by the lemma above, we can extend A to an assignment to φ′ that satisfies at least k = 7m clauses of φ′ simultaneously, which implies that (φ′,k) is a YES instance of max2sat.
Now, suppose that there is an assignment that simultaneously satisfies at least k = 7m clauses of φ′. Since the maximum number of clauses that can be satisfies within each group of 10 clauses is 7, this means that every group of 10 clauses has 7 clauses satisfied by the assignment. But by the lemma this means that this same assignment must satisfy every clause of φ, because if it didn’t satisfy even a single clause, then the associated group of 10 clauses of φ′ would only have 6 clauses satisfied by the current assignment. Thus we conclude that φ must be satisfiable.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com