Question 1: Write your name and student number.

Question 2: The set cover problem is defined as follows:

SETCovER = {(B, S1 , S2 , . . . , Sm , K) :   B is a finite set; m is an integer;

S1 , S2 . . . , Sm  are sets with uSi  = B; K is an integer;

there exists a subset I S {1, 2, . . . , m} of size K, such that uieISi  = B }.

Prove that the language SETCovER is in NP.

Question 3: The (0-1)-integer programming problem with K ones is defined as follows:

INTPRoc = {(A, K) :   A is an integer n x m matrix all of whose entries

are in {0, 1}; K is an integer;

there exists a binary column vector x of length m with exactly K ones, such that Ax > 1

(componentwise) },

where 1 denotes the column vector of length n, all of whose entries are equal to 1.

Prove that SETCovER <P  INTPRoc, i.e., in polynomial time, SETCovER can be reduced to INTPRoc.

Question 4: The subset sum problem is defined as follows:

SUBsETSUM = {(a1 , a2 , . . . , am , b) :   m, a1 , a2 , . . . , am , b are integers and

3I S {1, 2, . . . , m} such that    ieI ai  = b }.

Assume you have a polynomial-time algorithm A that decides, for any input sequence (a1 , a2 , . . . , am , b), whether or not (a1 , a2 , . . . , am , b) e SUBsETSUM. Note that this algorithm only returns YES or NO; it does not return anything else.

Design a polynomial-time algorithm B that takes an arbitrary sequence (a1 , a2 , . . . , am , b) as input.

● If (a1 , a2 , . . . , am , b) e SUBsETSUM, then B returns a subset I of {1, 2, . . . , m} such that    ieI ai  = b.

● If (a1 , a2 , . . . , am , b) e/ SUBsETSUM, then B returns NO.

Your algorithm B may use algorithm A as a black box. As always, justify your answer.

Question 5: The Hamilton cycle problem is defined as follows:

HAMILToNC×cLE = {G :  G is an undirected graph that has a Hamilton cycle}.

Let ϕ be a Boolean formula in the variables x1 , x2 , . . . , xn . We say that ϕ is in conjunctive normal form (CNF) if it is of the form

ϕ = C1 A C2 A . . . A Cm ,

where each Ci , 1 < i < m, is of the following form:

Ci  = l 1(i) v l2(i) v . . . v lk(i)i .

Each lj(i)  is a literal, which is either a variable or the negation of a variable.

The satisfiability problem is defined as follows:

SAT = {ϕ : ϕ is in CNF-form and is satisfiable}.

Prove that HAMILToNC×cLE <P  SAT, i.e., in polynomial time, HAMILToNC×cLE can be reduced to SAT.

Question 6: After being successful in implementing a superfast sorting algorithm, Lionel Messi decides to continue working as a software developer. Lionel looks again at his previous assignment, where he used Dijkstra’s algorithm to sort a sequence of numbers.  He realizes that he showed that the sorting problem can be reduced to one run of Dijkstra’s algorithm. Suddenly, Lionel actually understands the notion of polynomial-time reductions. Because of this, he decides to solve the P versus NP problem. Below, you find the proof of what is now known as

Messi’s Theorem: P = NP.

Let ϕ be a Boolean formula in the variables x1 , x2 , . . . , xn .

We say that ϕ is in conjunctive normal form (CNF) if it is of the form

ϕ = C1 A C2 A . . . A Cm ,

where each Ci , 1 < i < m, is of the following form:

Ci  = l 1(i) v l2(i) v . . . v lk(i)i .

Each lj(i)  is a literal, which is either a variable or the negation of a variable. We say that ϕ is in disjunctive normal form (DNF) if it is of the form

ϕ = C1 v C2 v . . . v Cm ,

where each Ci , 1 < i < m, is of the following form:

Ci  = l 1(i) A l2(i) A . . . A lk(i)i .