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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What result does the Cook-Levin Theorem prove?

A

SAT is NP complete

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

P = NP

How well did you know this?
1
Not at all
2
3
4
5
Perfectly