CS 21 Decidability and Tractability Winter 2024
Out: February 14
Due: February 21
Problem Set 5
Copyright By PowCoder代写 加微信 powcoder
Reminder: you are encouraged to work in groups of two or three; however you must turn in your own write-up and note with whom you worked. You may consult the course notes and the text (Sipser). The full honor code guidelines and collaboration policy can be found in the course syllabus.
Please attempt all problems. Please select one the last two problems to be graded completely (and indicate clearly which one); the other one will receive 1 point for a credible attempt. Please turn in your solutions via Gradescope, by 1pm on the due date.
1. A graph G is called k-colorable if there is a way to assign a color to each vertex so that no edge has both endpoints assigned the same color, using at most k distinct colors.
(a) Show that the language
2-colorable = {G : G is 2-colorable} is in P by reducing it to a problem known to be in P.
(b) Show that the following language is NP-complete: 3-colorable = {G : G is 3-colorable}.
Hint: reduce from 3-SAT. Your graph will contain 1 vertex for each literal, and 3 special vertices connected in a triangle (which must then be colored with the three distinct colors). You may find this observation useful: in the following graph,
if each of the grey nodes are colored with one of two colors, then it is possible to extend this coloring to a 3-coloring if and only if at least one of the three grey nodes on the left has the same color as the one on the right.
2. Let (3, 3)-SAT be the language consisting of satisfiable CNF formulas with at most 3 literals per clause, and at most 3 occurrences of any variable. Show that (3, 3)-SAT is NP-complete.
3. max2sat is the language consisting of all pairs (φ, k) where φ is a 2-CNF formula for which it is possible to simultaneously satisfy at least k clauses. Show that max2sat is NP-complete. Hint: how many of the following clauses can be satisfied as a function of x, y and z?
(x ∨ x), (y ∨ y), (z ∨ z), (w ∨ w), (¬x ∨ ¬y), (¬y ∨ ¬z), (¬z ∨ ¬x), (x ∨ ¬w), (y ∨ ¬w), (z ∨ ¬w)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com