NP Completeness Flashcards
1
Q
Poly Time Reducible
A
A language A is poly time reducible to B, if a poly time computable f exists such that w ∈ A iff f(w) ∈ B
2
Q
Given A is poly time reducible to B and B is in P, what can we conclude about A?
A
A is in P
3
Q
What result does the Cook-Levin Theorem prove?
A
SAT is NP complete
4
Q
What conditions must be satisfied for NP completeness?
A
L is NP complete if:
- L ∈ NP
- ∀A ∈ NP, A is poly time reducible to L
5
Q
Given: L is NP complete, L is poly time reducible to B, and B ∈ NP, what can we conclude about B?
A
B is NP complete
6
Q
Given: L is NP complete and L ∈ P, what can we conclude?
A
P = NP