CS 172: Computability and Complexity, Spring 2010 S. A. Seshia & O. EtesamiMidterm 2April 14, 2010YOUR NAME:Instructions:This exam is open-book, open-notes. Please turn off and put away electronic devices suchas cell phones, laptops, etc.You have a total of 75 minutes. There are 4 questions worth a total of 100 points. Thequestions vary in difficulty, so if you get stuck on any question, it might help to leave it fora while and try another one.Answer each question in the space provided below the question. If you need more space,you can use the reverse side of that page. You can use without proof any result proved inclass, in Sipser’s book, or on homeworks, but clearly state the result you are using.Do not turn this page until the instructor tells you to do so!Problem 1Problem 2Problem 3Problem 4Total1Problem 1: [True or False, with justification] (30 points)For each of the following four questions, state TRUE or FALSE. Justify your answer witha short proof or simple counterexample.(a) Let A be NP-complete and B be NP-hard. Then B ≤PA.(b) The set of all Turing-recognizable languages is countably infinite.(c) If L1and L2are Turing-recognizable, then L2\ L1is also Turing-recognizable.2Problem 2: (25 points)Let B = {hQ, Σ, Γ, q0, qaccept, qreject, n, wi | there are at least n transition functions δsuch that the Turing machine (Q, Σ, Γ, δ, q0, qaccept, qreject) accepts the string w}.Prove that B is undecidable.3Problem 3: (20 points)A Random-Access Turing machine (RA-TM) is similar to the standard, single-tape, deter-ministic TM except for its transition function. On a transition, a RA-TM can move its heada finite, but arbitrary distance from its current location. Formally, the transition function isδ : Q × Γ → Q × Γ × ({L, R} × N)For example, δ(qi, b) = (qj, c, (L, n)) will cause the RA-TM’s head to move n places to theleft (stopping at the left-most cell if the jump would cause the head to move off the tape).Prove that every RA-TM has an equivalent standard, single-tape, deterministic TM.4Problem 4: (25 points)Given a graph G = (V, E), an independent set is a set of vertices V0such that V0⊆ V andno two vertices in V0are connected by an edge in E.The problem of determining the maximum-size independent set in a graph is known to beNP-complete. Here is the decision version of that problem:IS = {hG, ki|G is an undirected graph with an independent set of size k}In this question, we investigate two related problems. (Be sure to turn the page for thesecond part!)(a) Suppose that G is a tree. Consider the following special case of the INDSET problem:IST = {hG, ki|G is an undirected tree with an independent set of size k}Show that IST ∈ P.5(b) Now consider the following variant of the problem of finding the independent set ina general undirected graph.SpecialIS = {hG, k, vi | G is an undirected graph with an independent set of size kthat includes vertex v}Show that SpecialIS is