CSCC63 Assignment 3 Due 11:59pm, April 3 Warning: Your electronic submission of a PDF to Crowdmark (through Quercus) affirms that this as- signment is your own work and no one else’s, and is in accordance with the University of Toronto Code of Behaviour on Academic Matters, the Code of Student Conduct, and the guidelines for avoiding plagiarism in CSCC63. Note that using Google or any other online resource is considered plagiarism. We stated in class that a number of languages are NP-complete: these include 3SAT, Clique, 3COL, VC, Subset-Sum, and Ham-Path. You may assume that these languages are NP-complete here. You may also refer to the fact that 2SAT and 2COL are in P. 1. (15 marks) (a) (5 marks) Consider the language 3DNF-SAT: INPUT: A Boolean formula φ in 3DNF. QUESTION: Is φ satisfiable? Show that 3DNF-SAT is in P. (b) (10 marks) Suppose someone comes up and tries to sell you a polytime algorithm to solve SAT: On input φ: 1. Set f = ¬φ. 2. Find an equivalent 3CNF f ′ to f . (We know from Cook’s theorem that we can do this with at most a quadratic blowup.) 3. Negate f ′ to get a 3DNF φ′. 4. Use your result from part (a) of this question to determine whether φ′ is satisfiable. We think that P6=NP, so there’s probably something wrong here. . . What’s wrong with the above algorithm? 2. (15 marks) Consider the language Disjoint-Ham-Path: INPUT: A directed graph G, along with two nodes s and t. QUESTION: Does G have two edge-disjoint Hamiltonian paths from s to t that have the same length? Show that Disjoint-Ham-Path is NP-complete. 3. (15 marks) Consider the language 3-Clique-Decomposition: INPUT: A graph G. QUESTION: Can G be split into three disjoint cliques? Show that 3-Clique-Decomposition is NP-complete. 4. (15 marks) Consider the language Partition: INPUT: A set S = { x1, x2, . . . , xn } of integers. QUESTION: Is there some subset X ⊆ S such that ∑x∈X x = ∑x∈S\X x? Show that Partition is NP-complete. 1 5. (15 marks) Recall the language Partition-Into-Triangles from class: INPUT: A graph G. QUESTION: Can G be split into disjoint triangles? We argued in class that we can show this language is NP-complete using a reduction from 3SAT. We’ll do that reduction here. Recall that when we reduced to Subset-Sum, we encoded three properties from our input φ from 3SAT: • The truth assignments to the variables, • the truth values of the clauses, and • the extra buffer variables to make everything work out evenly. We’ll to the same here. You’ll get a widget to encode a truth assignment into the Partition-Into- Triangles problem, and you’ll extend this widget to cover the other two properties. So here’s a widget for truth assignments. Suppose we have a formula φ = (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) We’ll create the following widget for all of the variables (this one is for x1): x1 x1 x1 x1 x1 x1 c1 c1 c2 c2 c3 c3 •• • • • • • • • • • • So we have two triangles for each clause in φ. The inner nodes don’t connect to anything else, and the outer nodes can be connected. You can see that if we try to break this graph into triangles, there are two ways of doing it — we can choose the ones labeled x1 (the solid grey), or we can choose the ones labeled x1 (the striped ones). Your job is to extend this idea to a full reduction from 3SAT by creating graph widgets to encode the second and third properties above, and then connecting them to the outer nodes on the above widgets. 2 6. (15 marks) In class we argue that it is NP-hard to determine the number of cycles in a graph. Fill in the details for this argument, and argue that if you could approximate this number to within a factor of two, then P would be equal to NP. 7. (10 marks) In statistical learning theory we are often interested in how powerful a type of classifier can be. One way of formalizing classifier power is to ask, what is the smallest set that this classifier cannot handle? This is basically something we call the VC-dimension of a classifier (it’s one plus the dimension, actually). Now, determining the VC-dimension of a classifier can be very difficult. We’ll look at a particular example here. Let the language VCCycle be defined as follows: INPUT: A directed graph G = (V,E), and a number k ∈ N. QUESTION: Is there a subset S ⊆ V of size k such that, for any X ⊆ S, X = c ∩ S for some cycle c in G? Show that VCCycle is in PSPACE (Note: this is probably not in NP). 8. Bonus (10 marks — your mark will be rounded to the nearest multiple of 2.5) Recall the reduction from 3SAT to Clique that we did in class. Change this reduction to make it parsimonious (try to make it one-to-one, like we did for Subset-Sum in tutorial 8). 3
