1
Q
What is the Cook-Levin Theorem?
A
SAT is NP-hard.
2
Q
Explain Valid(h) and Best(h) for the Stable Matching problem.
A
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)
Algorithms & Complexity
flashcards
Decks in class (8)
# Cards
