Extra credit$)$ Recall the course scheduling problem: Given h time slots and a set of

courses, each has a list of students. Determine if you can schedule the given courses into h

slots so that there is no conflict, i$.$e$.,$ no slot has two courses with a same student.

We have formulated this problem as a language named Schedule and proved that Schedule

is in NP$.$ Now you will show that it is NP$-$complete by proving that $3$Sat $$P Schedule.

To prove this, let be a $3$cnf$-$formula with n Boolean variables x$1,...,$ xn and k clauses

c$1,...,$ ck$,$ we construct an instance of Schedule as follows:

$$ Let the pool of all students be $\{$s$1,$ s$2,...,$ sn$+1\}.$

$$ For each variable xi$,$ where i $=1,...,$ n$,$ introduce three courses namely Xi$,$ Xi and Yi$.$

Course Xi contains only one student si$.$ Course Xi also contains only one student si$.$

Course Yi contains all but student si$.$

$1$

$$ For each clause cj $,$ where j $=1,...,$ k$,$ introduce a new course named Cj that contains

all students except for students si such that literals xi or $$xi appear in clause cj $.$

$$ Let the number of time slots be n $+1.$

In order to show that this is a polynomial time reduction from $3$Sat to Schedule, you need

to

$($a$)(5$pts$)$ Prove that if is satisfiable then there is a conflict$-$free schedule for the courses

introduced above into n $+1$ slots. $($Hint: Note that all courses Yi$$s contain student

sn$+1.)$

$($b$)(5$pts$)$ Prove that if there is a conflict$-$free schedule for the courses introduced above into

n $+1$ slots then is satisfiable.

$($c$)(5$pts$)$ Prove that the construction of courses above can be computed in polynomial time

in n and k$.($Hint: Give an upper bound estimation of the running time taken by a

multi$-$tape deterministic Turing machine to list all courses above and their students.$)$