This problem is called Set-Exact-Cover problem. Given a set U and a collection S

Question

This problem is called Set-Exact-Cover problem. Given a set U and a collection S of subsets of U, the question is whether there is a sub-collection S' of S, such that each element of U is in exactly one subset from the sub-collection S'.

(a) Prove that this problem is NP-complete.

(b) Prove that the above problem remains NP-complete when each member in S is a subset of U consisting exactly three elements.

(c) How about the same problem is each member in S is a subset of U consisting exactly two elements?

Explanation / Answer

(a) Prove that this problem is NP-complete:

Definition of NP:

A problem is said to be Nondeterministically Polynomial (NP) if we can find a nodeterminsitic Turing machine that can solve the problem in a polynomial number of nondeterministic moves.

We use NP to designate the class of all nondeterministically polynomial problems.

Clearly, P is a subset of NP

NP-Completeness:

A problem R is NP complete if

An equivalent but casual definition: A problem R is NP-complete if R is the "most difficult" of all NP problems.

Theorem: Let P and R be two problems. If P reduces to R and R is polynomial, then P is polynomial.

Proof: Let T be the transform that transforms P to R. T is a polynomial time algorithm that transforms IP to IR such that Answer(QP,IP) = Answer(QR,IR)

Let AR be the polynomial time algorithm for problem R. Clearly, A takes as input IR, and returns as output Answer(QR,IR)

Design a new algorithm AP as follows:

Algorithm AP(input: IP)
begin
IR := T(IP);
x := AR(IR);
  return x;
end

Note that this algorithm AP returns the correct answer Answer(QP,IP) because x = AR(IR) = Answer(QR,IR) = Answer(QP,IP).

Note also that the algorithm AP takes polynomial time because both T and AR
Q.E.D.

The intuition derived from the previous theorem is that if a problem P reduces to problem R, then R is at least as difficult as P.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.