VL-14: Der Satz von Cook & Levin Flashcards
1
Q
Was besagt der Satz von Cook & Levin?
A
Alle Probleme in NP lassen sich auf SAT reduzieren in polynomialer Zeit
2
Q
Was ist die Definition von NP-schwer?
A
Ein Problem L* heißt NP-schwer falls gilt:
∀L∈ NP: L ≤p L*
Beispiel: SAT
3
Q
Wann ist ein Problem NP-vollständig? (NP-complete)
A
Ein Problem L ist NP-vollständig wenn es in NP ist und NP-schwer ist.
Beispiel: SAT
4
Q
Wie zeigt man, dass ein Problem NP-vollständig ist?
A
- Zeige dass das Problem L in NP liegt
- Wähle ein Problem L* das NP-schwer ist und zeige L* ≤ L
- Konstruiere Funktion f die Eingaben von L* auf L abbildet
- Zeige polynomielle Zeit
- Zeige Korrektheit
