Week 1 (P vs NP, Stable Matching) Flashcards
(22 cards)
What is the class P?
The class of problems solvable in polynomial time by a deterministic TM
What is the class NP?
The class of problems verifiable in polynomial time by a deterministic TM but solvable in polynomial time by a non-deterministic TM
What is a reduction?
A reduction transforms a problem A into a problem B such that if you can solve problem B efficiently you can solve problem A efficiently.
What is the notation for a polytime redutcion?
Y ≤p X
What is a NP-hard problem?
A problem is NP-hard if for all problems Y ∈ NP, Y ≤p X
How do we prove a problem is NP-hard?
By reducing any known NP-hard problem such that SAT ≤p X
What is the Cook-Levin theorem?
The Cook-Levin theorem states CNF-Satisfiability (SAT) is NP-hard
How do we prove almost-SAT?
Given a CNF formula with N variables and M clauses, Almost-SAT satisfies exactly M-1 clauses.
For an instance of SAT I, Almost SAT I’ = I ∧ (y) ∧ (ȳ).
If all clauses of I are satisfiable, then all but one clause of I’ is satisfiable.
This reduction works in polynomial time as we have M+2 clauses.
What instances of SAT can be proved in polynomial time?
1-SAT and 2-SAT
What is the max clause length for SAT?
2N as each variable can be y or ȳ
How can we prove the independent set is NP-hard?
By taking an instance I of 3-SAT and building a graph G of 3M vertices. We add edges as conflicts to ensure every variable is not True and False.
I is satisfiable iff G has an independent set of size M.
Takes (N+M)^O(1) time
What is said about NP-hard problems if we assume P != NP?
A NP-hard problem cannot have an algorithm that is both always correct and runs in polynomial time.
What is CNF?
A conjunction of clauses where each clause is a disjunction of literals
(and of ors)
What is the brute force time for SAT?
Checking 2^N truth assignments for N variables and M clauses
=> O(2^N . N . M)
What is the independent set problem?
Given an undirected graph G=(V,E) of n vertices, a set X has no pair of vertices that form an edge
What is the stable matching problem?
Aims to find a stable matching where there are no unstable pairs.
What is an unstable matching?
An pair is unstable if there is a higher preference to their current partner.
What is the Gale-Shapley algorithm?
Initially all hospitals and students are free
while There is a hospital which is free and hasn’t made an offer to every
student do
Choose such a hospital h
Let s be highest ranked student to which h hasn’t made an offer yet
if s is free then
(s, h) are matched
else
s is currently matched to some hospital h′
if s prefers h′ to h then
h remains free
else
s prefers h to their current match h′
(s, h) get matched and h′ becomes free
end if
end if
end while
What is the output of the Gale-Shapley algorithm?
Gale-Shapley always returns a stable matching in O(N^2) time
What happens to the offers of students vs hospitals as the Gale-Shapley algorithm progresses?
The side that sends out offers, i.e. the hospitals, send out worse offers as the algorithm progresses but the side that receives offers, i.e. the students, receive better offers as the algorithm progresses.
Argue the correctness and running time of the Gale-Shapley algorithm
The algorithm is correct as if there is a hospital that is free, then there is a student that hasn’t received an offer yet.
Prove that the Gale-Shapley algorithm always returns a stable matching
If we assume Gale-Shapley doesn’t return a stable match, let (h,s) and (h’,s’) be an allocation made.
The last match was (h,s)
If h didn’t make an offer to s’ before s, then h prefers s to s’ => contradiction
If h did make an offer to s’ before s, then h was rejected by s’ in favour of a different hospital => contraditcion
