Week Three

Question 1

What is the Cook-Levin Theorem?

Answer 1

SAT is NP-hard.

Question 2

Explain Valid(h) and Best(h) for the Stable Matching problem.

Answer 2

Valid(h) = {s : There is a stable matching which matches h to s}

Best(h) is the highest ranked (in preference list of h) student from Valid(h)