CSCI 570 – HW 10 Due: November 20th
Graded Problems
1. State True/False
(a) Assume P ̸= NP. Let A and B be decision problems. If A ∈ NPC
andA≤p B,thenB∈P.
False. IfBwereinP,thenA≤p BwouldimplyA∈P. Since A∈NPC,∀D∈NP,D≤p A. SinceA≤p B,thisimplies ∀D ∈ NP,D ∈ P which contradicts P ̸= NP.
(b) If someone proves P=NP, then it would imply that every decision problem can be solved in polynomial time.
False. Halting is a counter example.
(c) IfA≤p BandB∈NP,thenA∈NP.
True. Proof : B ∈ NP implies that there exists a polynomial time verifier VB and a constant kB such that x ∈ B if and only if there exists a cx such that ||cx|| ≤ ||x||k and VB(x,cx) = 1. Here, ||y|| denotes the number of bits used to write y.
Let f : N −→ N be a polynomial time reduction from A to B with running time bounded by a polynomial of degree d. Compose the algorithms VB and f to obtain the polynomial time algorithm VA, that is
VA(w) := VB(f(w)),∀w ∈ N
We claim that VA is a verifier for A with certificate size bounded by
kd bits.
If w ∈ A, then f(w) ∈ B and f(w) is at most ||w||d bits long. Hence ∃cf(w) such that ||cf(w)|| ≤ ||f(w)||k ≤ ||w||dk and VB(f(w),cf(w)) = 1.
1
Conversely, if there exists c ̄w such that ||c ̄w || ≤ ||w||kd and VB (f (w), c ̄w ) = 1,thenf(w)∈B→w∈A. HenceourclaimistrueandA∈NP.
2. 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 number is a certificate. Verification proceeds by dividing the number by the factor and making sure that the reminder is zero. The factor is at most n nits and verification can be done in time polynomial in n. Thus deciding if a number is composite is in NP.
3. State True/False. Assume you have an algorithm that given a 3-SAT in- stance, decides in polynomial time if it has a satisfying assignment. Then you can build a polynomial time algorithm that finds a satisfying assign- ment(if it exists) to a given 3-SAT instance.
True. Pick the first literal in the first clause (call it x1). Replace x1 with 1 (or 0) and ¬x1 with 0 (or 1) in every mention of x1 and ¬x1 in the satisfying problem. Run the deciding algorithm. If the problem is still satisfiable we go to the next literal (if needed in the next clause) and we do the same process until all the literals are assigned value. If the problem is not satisfiable, this implies that we have set the literal with a wrong value. Then we change the value from 1 to 0 (or 0 to 1) and again we continue with rest of the literals.
4. Show that vertex cover remains NP-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
2
if and only if G has a vertex cover of size k.
Practice Problems
5. Given an integer m × n matrix A and an integer m − vectorb, the 0- 1integer programming problem asks whether there exists an integer n − vectorx with elements in the set {0; 1} such that Ax = b. Prove that 0-1integer programming is NP Complete. (Hint: Reduce from 3-CNF- SAT.)
Given an x, one can easily verify in polynomial time whether Ax ≤ b, hence, the 0-1 integer-programming problem is in NP. 3-CNF-SAT ≤p 0-1 INTEGER-PROGRAMMING, that is we reduce the 3-CNF-SAT prob- lem to the 0-1 integer-programming problem to show NP-completeness. Let the 3-CNF-SAT problem have n variables. A variable x in integer- programming corresponds to a (0, 1)-integer variable x, the negation of x corresponds to (1 − x). Now each clause would be converted into a row of A. So for example, the clause x or (not y) or z is going to be converted to x + (1 − y) + z ≥ 1 which is equal to −x + y − z ≤ 0.
3