CSCI570 Summer2015 HW8 1 State True False If A p B and B N P then A N P True The important observation is that you can construct a certifier for A by composing the polynomial time reduction map and the certifier for B A proof sketch 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 for B then c CB x c 0 and if x B then there exists a cx such that cx x k and CB x cx 1 Here y denotes the number of bits used to write y Let f be a polynomial time reduction from A to B with running time bounded by a polynomial of degree d That is f is a polynomial time algorithm 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 Compose the algorithms CB and f to obtain the polynomial time algorithm CA that is x c CA x c CB f x c We claim that CA is a polynomial time certifier for A with certificate size bounded by kd bits 2 State True False If A p B and A N P complete then B N P complete False If A p B and A N P complete then B is not necessarily in N P complete since B need not be in N P 3 State True False Assume you have a polynomial time algorithm that given a 3 SAT instance decides in polynomial time if it has a satisfying assignment Then you can build a polynomial time algorithm that finds a satisfying 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 cm be the boolean formula corresponding to a 3 SAT instance where c1 c2 cm are the clauses and x1 x2 xn are the variables 1 If A x1 x2 xn 0 then return that the instance is non satisfiable If A x1 x2 xn 1 then we can find an assignment for x1 as follows If A 1 x2 xn 1 then we can set x1 1 and be guaranteed that 1 1 x2 xn is satisfiable Else we can set x1 0 and be guaranteed that 1 0 x2 xn is satisfiable In either case we know 1 has a satisfying assignment That is there exists a satisfying assignment for that assigns to x1 the same assignment that our algorithm made In the second iteration we find an assignment for x2 given that we have already made a choice for x1 If A 1 1 x3 xn 1 we can set x2 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 which is nothing but the evaluation of at this assignment is 1 4 State True False If someone proves P N P then it would imply that every decision problem can be solved in polynomial time False If P N P then we can conclude that every problem in N P can be solved in polynomial time However there are decision problems that are not in N P that are known to not have polynomial time algorithms One such example is the Halting problem which cannot be solved even if there were no restriction on the resources like time or space 5 State True False Assume P 6 N P Let A and B be decision problems If A N P Complete and A P B then B P True If B were in P then A p B would imply A P Since A NPComplete D NP D p A Since A p B this implies D NP D P which contradicts P 6 NP 6 State True False Assume P 6 N P Let A and B be decision problems If A P and B N P Complete then A P B True B NP Complete implies D NP D P B Since P NP A P B 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 the 2 number is a certificate Certification proceeds by dividing the number by the factor and making sure that the reminder is zero and also making sure that the certificate is neither 1 nor the input number itself The factor is at most n bits and verification can be done in time polynomial in n Thus deciding if a number is composite is in NP 8 Show that vertex cover remains N P Complete even if the instances are restricted 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 each of the vertices with which it is incident the sum of the degrees of the vertices is exactly 2 E an even number Hence there is an even number of 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 V0 is even Since a vertex cover for a triangle is of minimum size 2 it is clear that G has a vertex cover of size k 2 if 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 decide if there is a subset A V of vertices satisfying the following two conditions i A V2 ii For every pair of vertices u v A if u 6 v then u v E Show that Half Clique is in N P Complete You are allowed to use the fact that Independent Set is in N P Complete Given a set of vertices A as the certificate it is easy to verify that the two conditions listed in the question are satisfied Thus Half Clique is in NP We will reduce Independent set to Half Clique in two steps The intermediate step concerns the Clique problem We begin by defining a few terms that we require A subset of vertices is called as a clique if and only if every distinct …