CSCI 0510 Models of Computation HW11 Due: Dec 4, 2014 Include your full name, CS login, and the problem number(s) on each piece of paper you hand in, and please staple your pages together before handing in. While collaboration is encouraged in this class, please remember not to take away notes from any collaboration sessions. Also please list the names and logins of any of your collaborators at the beginning of each homework. Please monitor the mailing list, as we will post clarifications of questions there. You should hand in your solutions to the CSCI 51 bin on the second floor of the CIT. Late homeworks are not accepted. Problem 1 Consider the following randomized approximation algorithm for computing a vertex cover. Algorithm SomeCover = “On input G = {V, E}: 1. L ← ∅ 2. while E 6= ∅: • pick a random (x, y) ∈ E and remove it from E • L ← L ∪ {x, y} • remove from E all edges containing either x or y 3. return L” (a) Prove that this algorithm produces a correct, but not necessarily minimal, vertex cover. (b) Is this a polynomial time algorithm? Briefly explain your answer. (c) Describe how the contents of the random tape of a Turing machine performing this algorithm would affect the results. That is, explain a worst case scenario for the output of this algorithm. CSCI 0510 Due: Dec 4, 2014 (d) Let k be the smallest possible size of a vertex cover for a graph. Prove that this algorithm produces a vertex cover whose size is no more than 2k. Problem 2 A probabilistic Turing machine is a Turing machine that, in addition to the usual tape, also has a second tape filled with random bits. A probabilistic Turing machine may sometimes accept, and sometimes reject the same input x, depending on the content of the random tape. There are three main probabilistic polynomial-time complexity classes, BPP, RP, coRP, and they are defined as follows1 : • A language L is in BPP if there exists a probabilistic Turing machine M that runs in polynomial time such that the following two conditions hold: Completeness For every x ∈ L, Pr[M accepts x] ≥ 2/3. Soundness For every x ∈ / L, Pr[M accepts x] ≤ 1/3. This Turing machine M is called a Monte-Carlo algorithm for L. • A language L is in RP if there exists a Turing machine M that runs in polynomial time such that the following two conditions hold: Completeness For every x ∈ L, Pr[M accepts x] ≥ 2/3. Perfect soundness For every x ∈ / L, Pr[M accepts x] = 0. • A language L is in coRP if its complement is in RP. (a) Show that P⊆RP⊆BPP and P⊆coRP⊆BPP. (b) Show that the class coRP can be equivalently defined as follows: A language L is in coRP if there exists a Turing machine M that runs in polynomial time such that the following two conditions hold: Perfect completeness For every x ∈ L, Pr[M accepts x] = 1. Soundness For every x ∈ / L, Pr[M accepts x] ≤ 1/3. 1 There are several equivalent ways of defining them, some of which are discussed in Lab Problem 2; different texts may present slightly different definitions. 2 CSCI 0510 Due: Dec 4, 2014 Problem 3 Show that TQBF, the language of true quantified Boolean formulas is still PSPACE-complete when the part following the quantifiers is in 3-CNF. The following questions are lab problems. Lab Problem 1 Recall the decision problem 3SAT, where we had to determine whether there was some assignment of truth values that satisfies every clause of a 3CNF. In the optimization version MAX-3SAT, the goal is to find some assignment of truth values that satisfies the maximum possible number of clauses, even if it is not possible to satisfy every single clause. Design a polynomial time algorithm that, given as input a boolean formula in 3CNF, finds an assignment of values that satisfies at least 7/8’s as many clauses as the maximum possible number of satisfiable clauses. You should assume that each clause contains exactly 3 literals of distinct variables. Hint: The algorithm should set each variable in the formula one by one, depending on the expected number of satisfied clauses given a particular assignment. That is the algorithm should choose an assignment to variable xi based on the expected number of satisfied clauses given that xi = 1 and the expected number of satisfied clauses given xi = 0. Lab Problem 2 In this problem, you will show the equivalence of several different definitions for a fourth important probabilistic complexity class, ZPP. A language L is in ZPP if there exists a probabilistic Turing machine M that, in addition to the usual accepting and rejecting states, has an “unsure” state in which the machine can halt. M will run in polynomial time and at termination time will be in accept, or reject, or unsure state, with the following guarantees: Completeness For every x ∈ L, Pr[M accepts x] ≥ 2/3, Pr[M rejects x] = 0, and Pr[M is unsure on x] ≤ 1/3. Soundness For every x ∈ / L, Pr[M accepts x] = 0, Pr[M rejects x] ≥ 2/3, and Pr[M is unsure on x] ≤ 1/3. 3 CSCI 0510 Due: Dec 4, 2014 (a) Using the definitions presented in Homework Problem 2, show that ZPP=RP∩coRP. (b) Using either of the above definitions for ZPP, demonstrate that the following definition is also equivalent. A language L is in ZPP if there exists a probabilistic Turing machine M (which does not have “unsure” states) and some polynomial p such that: Runtime For all input x of length n, E[runtime of M on x] ∈ O (p(n)). Completeness For every x ∈ L, Pr[M accepts x] = 1. Soundness For every x ∈ / L, Pr[M accepts x] = 0. This Turing machine M is called a Las Vegas algorithm for L. Lab Problem 3 Recall Lab Problem 2 from Homework 9, where Colbert was trying to win the space race by building a spaceship a stack of hull plates. Colbert has now learned that there is a Russian spy attempting to sabotage his spaceship by changing the configuration of some of the hull plates in the stack. Because of Colbert’s stubborn patriotism, the spy’s own dogmatic ideals, and some unexpected addendums to the Geneva Conventions, there are very specific ways that the spy can sabotage Colbert’s stack, and how Colbert can counter the spy’s attempts at sabotage. The rules of the conflict are as follows. Colbert and the spy both have a stack of hull plates, which they cannot reorder, and Colbert first sets down the top hull plate in his stack, choosing which side to face up (just as in the problem PlateFill). The two then take turns taking the top hull plate from their stack and placing it on top of the common stack, choosing which side faces up. Colbert wins if all holes are filled, and the spy wins if there is some hole position that is unblocked. Show that the problem of determining whether Colbert or the spy has a winning strategy for a given starting configuration of hull plates is PSPACE-complete. 4