Consider the problem of determining if k classes at some university can have the

Question

Consider the problem of determining if k classes at some university can have the final exam scheduled at the same time. In this problem, a class C is a set (of students), and two classes can have the exam at the same time, if they have no common student. So the problem is SIMULTANEOUS EXAM SCHEDULING (SES).

(a) Show that SES is in NP. (Say what a certificate of a YES-instance of SES is).

c) Consider the following instance of SES: C1 = {1, 2, 7}, C2 = {2, 3, 5}, C3 = {1, 4, 6}, C4 = {7, 8, 9}, C5 = {3, 4, 8} and k = 3. Draw the graph G obtained from this instance of SES with your reduction in (b).

Explanation / Answer

K classes -final listed at same occasion

C class-Set of student and two group of students have the last at the similar occasion

Answer:

First, we must show that SES ? NP by presentation that a answer can be recognized in polynomial

time. We first confirm that | C |= k. Then, we confirm

for each student form the group of students C C1 ? K,C2 ? K.....Cn ? K and choose two student from class Cn and K who make a put out of place couple.

time. Thus, the answer can be established in polynomial time, and IS ? NP.

Second, we must show that SES ? NP by presentation that a known NP-Complete difficulty

reduces to SES; namely, we show that SES ?P CLIQUE , i.e., there is a polynomial-time

reduction f of any CLIQUE difficulty to an SES difficulty such that C1,C2..Cn ? CLIQUE if

and only if K ? IS. The class K form an self-governing set of student with class c. Therefore, the NP-Complete CLIQUE difficulty is poly-time

reducible to SES.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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