NP Completeness

Question 1

Poly Time Reducible

Answer 1

A language A is poly time reducible to B, if a poly time computable f exists such that w ∈ A iff f(w) ∈ B

Question 2

Given A is poly time reducible to B and B is in P, what can we conclude about A?

Answer 2

A is in P

Question 3

What result does the Cook-Levin Theorem prove?

Answer 3

SAT is NP complete

Question 4

What conditions must be satisfied for NP completeness?

Answer 4

L is NP complete if:
- L ∈ NP
- ∀A ∈ NP, A is poly time reducible to L

Question 5

Given: L is NP complete, L is poly time reducible to B, and B ∈ NP, what can we conclude about B?

Answer 5

B is NP complete

Question 6

Given: L is NP complete and L ∈ P, what can we conclude?

Answer 6

P = NP