CSCI570-Summer2015-HW81. State True/False. If A ≤pB and B ∈ NP , then A ∈ NP . True. Theimportant observation is that you can construct a certifier for A by com-posing the polynomial time reduction map and the certifier for B. A proofsketch for Karp reductions follows if you are interested.Proof : B ∈ NP implies there exists a polynomial time certifier CB.That is, there exists a constant k such that, if x is a “no” instance forB then ∀c, CB(x, c) = 0 and if x ∈ B then there exists a cxsuch that||cx|| ≤ ||x||kand CB(x, cx) = 1. Here, ||y|| denotes the number of bitsused to write y.Let f be a polynomial time reduction from A to B with running timebounded by a polynomial of degree d. That is, f is a polynomial timealgorithm that maps instances of A to instances of B, such that x is an“yes” instance of A if and only if f (x) is a “yes” instance of B. Composethe algorithms CBand f to obtain the polynomial time algorithm CA,that is∀x, ∀c, CA(x, c) := CB(f(x), c)We claim that CAis a polynomial time certifier for A with certificate sizebounded by kd bits.2. State True/False. If A ≤pB and A ∈ NP -complete, then B ∈ NP -complete.False. If A ≤pB and A ∈ NP -complete, then B is not necessarily inNP −complete (since B need not be in N P ).3. State True/False. Assume you have a polynomial time algorithm thatgiven a 3-SAT instance, decides in polynomial time if it has a satisfyingassignment. Then you can build a polynomial time algorithm that finds asatisfying assignment(if it exists) to a given 3-SAT instance.True. Let A be a polynomial time algorithm that decides 3-SAT.Let φ(x1, x2, . . . , xn) = c1∧ c2∧ . . . ∧ cmbe the boolean formula cor-responding to a 3-SAT instance where c1, c2, . . . , cmare the clauses andx1, x2, . . . , xnare the variables.1If A(φ((x1, x2, . . . , xn))) = 0, then return that the instance is non sat-isfiable.If A(φ((x1, x2, . . . , xn))) = 1, then we can find an assignment for x1asfollows. If A(φ((1, x2, . . . , xn))) = 1, then we can set x1= 1 and be guar-anteed that φ1:= φ(1, x2, . . . , xn) is satisfiable. Else, we can set x1= 0and be guaranteed that φ1:= φ(0, x2, . . . , xn) is satisfiable.In either case, we know φ1has a satisfying assignment. That is, thereexists a satisfying assignment for φ that assigns to x1the same assign-ment that our algorithm made.In the second iteration, we find an assignment for x2given that we havealready made a choice for x1. If A(φ1(1, x3, . . . , xn)) = 1, we can setx2= 1 and φ2(x3, . . . , xn) = φ1(1, x3, . . . , xn). Else we can set x2= 0 andφ2(x3, . . . , xn) = φ1(0, x3, . . . , xn).By iterating, we find an assignment for the variables such that φn(whichis nothing but the evaluation of φ at this assignment) is 1.4. State True/False. If someone proves P = N P , then it would imply thatevery decision problem can be solved in polynomial time.False. If P = NP , then we can conclude that every problem in NPcan be solved in polynomial time. However, there are decision problems(that are not in NP ) that are known to not have polynomial time algo-rithms. One such example is the Halting problem which cannot be solvedeven if there were no restriction on the resources (like time or space).5. State True/False. Assume P 6= NP . Let A and B be decision problems.If A ∈ N P -Complete and A ≤PB, then B /∈ P .True. If B were in P, then A ≤pB would imply A ∈ P. Since A ∈ NP-Complete, ∀D ∈ NP, D ≤pA. Since A ≤pB, this implies ∀D ∈NP,D ∈ P which contradicts P 6= NP.6. State True/False. Assume P 6= NP . Let A and B be decision problems.If A ∈ P and B ∈ NP -Complete, then A ≤PB.True. B ∈ NP-Complete implies ∀D ∈ NP, D ≤PB. Since P ⊆ NP,A ≤PB. (Note that we dont use the assumption P 6= NP)7. Given an n bit positive integer, the problem is to decide if it is composite.Here the problem size is n. Is this decision problem in NP ?Yes. For every “yes” instance (the number is composite), a factor of the2number is a certificate. Certification proceeds by dividing the number bythe factor and making sure that the reminder is zero and also making surethat the certificate is neither 1 nor the input number itself. The factor isat most n bits and verification can be done in time polynomial in n. Thusdeciding if a number is composite is in NP.8. Show that vertex cover remains NP -Complete even if the instances arerestricted to graphs with only even degree vertices.Let < G; K > be an input instance of VERTEX-COVER, where G =(V ; E) is the input graph.Because each edge in E contributes a count of 1 to the degree of eachof the vertices with which it is incident, the sum of the degrees of thevertices is exactly 2|E|, an even number. Hence, there is an even numberof vertices in G that have odd degrees.Let U be the subset of vertices with odd degrees in G.Construct a new instance <¯G; k + 2 >of VERTEX-COVER, where¯G =(V0; E0) with V0= V ∪ {x, y, z} and E0= E ∪ {(x, y), (y, z), (z, x)} ∪{(x, v)|v ∈ U}. In words, we make a triangle with the three new vertices,and then connect one of them (say x) to all the vertices in U.The degree of every vertex in V0is even. Since a vertex cover for a triangleis of (minimum) size 2, it is clear that¯G has a vertex cover of size k + 2if and only if G has a vertex cover of size k.9. Given an undirected graph G = (V, E), the Half-Clique problem is to de-cide if there is a subset A ⊆ V of vertices satisfying the following twoconditions:(i) |A| ≥|V |2(ii) For every pair of vertices u, v ∈ A, if u 6= v, then (u, v) ∈ E.Show that Half-Clique is in NP -Complete. You are allowed to use thefact that Independent-Set is in NP -Complete.Given a set of vertices A as the certificate, it is easy to verify that the twoconditions listed in the question are satisfied. Thus Half-Clique is in NP.We will reduce Independent set to Half-Clique in two steps. The interme-diate step concerns the Clique problem.We begin by defining a few terms that we require. A subset of vertices iscalled as a clique if and only if every distinct pair of vertices in the sub-set is connected by an edge. Given a graph and a number m, the clique3problem is to decide if the graph has a clique of size m. For a graph G1,its complement (denoted by¯G1) is defined as the graph that has the samevertex set as G1, but …