Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Erklärung
Komplexitätsklassen P und NP
Sortieren geht schnell. Aber den optimalen Rundweg eines Paketboten zu finden? Das dauert bei vielen Städten praktisch ewig, obwohl man eine vorgeschlagene Route blitzschnell prüfen kann. Dieser Unterschied zwischen Lösen und Verifizieren ist der Kern der Klassen P und NP und der berühmtesten offenen Frage der Informatik: Gilt P = NP?
Was du in der Klausur können musst:
- P und NP über Lösen vs. Verifizieren definieren
- NP-vollständig und NP-schwer sauber unterscheiden
- die Rolle der polynomiellen Reduktion und von SAT (Cook-Levin)
- die Hierarchie
P ⊆ NP ⊆ PSPACE ⊆ EXPTIME
Die Idee in einem Satz
P sind die Probleme, die man in polynomieller Zeit lösen kann. NP sind die, deren Lösung man in polynomieller Zeit verifizieren kann (mit einem Zertifikat). Ob beide Klassen gleich sind (
P = NP), ist ungelöst.
P: effizient lösbar
P (polynomielle Zeit) enthält die Probleme, für die eine deterministische Maschine in O(n^k) Schritten die Antwort berechnet. Beispiele: Sortieren, kürzeste Wege (Dijkstra), Primzahltest (AKS). Diese gelten als "praktisch effizient lösbar".
NP: effizient verifizierbar
NP (nichtdeterministisch polynomiell) enthält die Probleme, bei denen man eine vorgeschlagene Lösung (ein Zertifikat) in polynomieller Zeit prüfen kann.
Wichtig: NP heißt nicht "nicht polynomiell", sondern nichtdeterministisch polynomiell. Äquivalent: eine nichtdeterministische TM löst es in polynomieller Zeit.
Beispiele: SAT (ist eine Boolesche Formel erfüllbar?), Travelling Salesman (gibt es eine Rundtour unter Länge k?), Rucksack, Graphfärbung. Eine konkrete Belegung bzw. Tour prüft man schnell, sie zu finden scheint dagegen schwer.
Es gilt P ⊆ NP: was man lösen kann, kann man auch verifizieren (die Lösung selbst ist das Zertifikat).
Die Hierarchie erkunden
Klicke auf eine Klasse und sieh ihre Definition und typischen Probleme. Die Klassen sind ineinander geschachtelt.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
NP-vollständig und NP-schwer
Um die "schwersten" Probleme in NP zu fassen, nutzt man die polynomielle Reduktion A ≤_p B: man übersetzt jede Instanz von A in polynomieller Zeit in eine von B. Dann ist B "mindestens so schwer" wie A.
| Begriff | Definition |
|---|---|
| NP-schwer | Jedes Problem aus NP ist auf dieses Problem polynomiell reduzierbar. Muss nicht selbst in NP liegen. |
| NP-vollständig | NP-schwer UND in NP. Die schwersten Probleme, die noch in NP liegen. |
SAT war das erste als NP-vollständig bewiesene Problem (Satz von Cook-Levin, 1971). Über Reduktionsketten folgten Tausende weitere (TSP, Rucksack, Cliquen, Graphfärbung).
Schlüsselaussage: Läge ein einziges NP-vollständiges Problem in
P, dann wäreP = NP, und alle NP-Probleme wären effizient lösbar. Genau deshalb ist dieP-vs-NP-Frage so bedeutsam.
Die offene Frage und ihre Folgen
P = NP ist ein Millennium-Problem (1 Mio. Dollar Preisgeld) und gilt als wahrscheinlich falsch (P ≠ NP), aber unbewiesen. Praktische Konsequenzen:
- Kryptographie beruht darauf, dass bestimmte Probleme (Faktorisierung u.a.) schwer sind,
P ≠ NPist die Hoffnung dahinter. - Für NP-schwere Probleme nutzt man Heuristiken, Approximationen und Spezialfälle statt exakter Polynomialalgorithmen.
Die bekannte Hierarchie: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME, und bewiesen ist P subsetneq EXPTIME (es gibt also nachweislich nicht effizient lösbare Probleme).
Klausur-Faustregeln
1. P = polynomiell LÖSBAR, NP = polynomiell VERIFIZIERBAR (Zertifikat). P ⊆ NP.
2. NP heißt nichtdeterministisch polynomiell, nicht "nicht polynomiell".
3. NP-vollständig = in NP UND NP-schwer. SAT ist das Urproblem (Cook-Levin 1971).
4. NP-schwer = mindestens so schwer wie alles in NP, muss aber nicht selbst in NP liegen.
5. Ein NP-vollständiges Problem in P ⇒ P = NP (für alle).
6. Polynomielle Reduktion A ≤_p B: B ist mindestens so schwer wie A. Um B als NP-schwer zu zeigen, reduziere ein bekanntes NP-schweres A auf B.
Häufige Stolpersteine
1. NP als "nicht polynomiell" lesen. Falsch. NP = nichtdeterministisch polynomiell = in polynomieller Zeit verifizierbar.
2. P ≠ NP als bewiesen ansehen. Es ist nur vermutet, nicht bewiesen. Das ist gerade die offene Frage.
3. NP-schwer und NP-vollständig gleichsetzen. NP-schwer muss nicht in NP liegen (das Halteproblem ist NP-schwer, aber nicht in NP, sogar unentscheidbar). NP-vollständig ist beides.
4. NP-Vollständigkeit unvollständig beweisen. Man braucht zwei Teile: (a) das Problem liegt in NP, und (b) ein bekanntes NP-vollständiges Problem ist darauf reduzierbar.
5. Verifizieren mit Finden verwechseln. NP-Probleme sind leicht zu prüfen, aber (vermutlich) schwer zu lösen. Das ist der ganze Punkt.
6. Reduktionsrichtung verdrehen. A ≤_p B bedeutet "A ist nicht schwerer als B". Um B als schwer zu zeigen, reduziert man das bekannte schwere A auf B, nicht umgekehrt.
Interaktiv verstehen
Klassen und Probleme zuordnen
Wähle eine Klasse und betrachte ihre Definition und Beispielprobleme. Achte besonders auf den Sprung von P (lösbar) zu NP (verifizierbar) und darauf, wo die NP-vollständigen Probleme sitzen.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Wenn du ein Problem als NP-vollständig einordnen sollst, nenne immer beide Teile: "liegt in NP (Zertifikat in poly Zeit prüfbar)" und "ist NP-schwer (Reduktion von einem bekannten NP-vollständigen Problem)".
Praxis-Übung
Klausurfragen mit Lösungen (6)
- F1.Was charakterisiert die Klasse P?
Antwort: Probleme, die man in polynomieller Zeit lösen kann
Erklärung: P enthält die Probleme, die eine deterministische Maschine in polynomieller Zeit O(n^k) löst. Beispiele: Sortieren, kürzeste Wege, Primzahltest.
- F2.Wofür steht das 'N' in NP?
Antwort: für 'nichtdeterministisch' (nichtdeterministisch polynomiell)
Erklärung: NP = nichtdeterministisch polynomiell. Es ist ein verbreiteter Irrtum, NP als 'nicht polynomiell' zu lesen. NP-Probleme sind in polynomieller Zeit verifizierbar.
- F3.Es gilt P ⊆ NP.
Antwort: Wahr
Erklärung: Richtig. Kann man ein Problem in polynomieller Zeit lösen, kann man eine vorgeschlagene Lösung erst recht verifizieren (man rechnet die Lösung einfach selbst aus). Also ist jedes P-Problem auch in NP.
Typ: Wahr/Falsch
- F4.Was bedeutet 'NP-vollständig'?
Antwort: in NP UND NP-schwer (jedes NP-Problem ist darauf reduzierbar)
Erklärung: NP-vollständig heißt: das Problem liegt selbst in NP und ist NP-schwer (jedes Problem aus NP lässt sich polynomiell darauf reduzieren). Es sind die schwersten Probleme innerhalb von NP. SAT ist das klassische Beispiel.
- F5.Welches Problem wurde zuerst als NP-vollständig bewiesen (Satz von Cook-Levin)?
Antwort: SAT (Erfüllbarkeit Boolescher Formeln)
Erklärung: Der Satz von Cook-Levin (1971) zeigte als erstes, dass SAT NP-vollständig ist. Von SAT ausgehend wurden per Reduktion Tausende weitere Probleme als NP-vollständig bewiesen.
- F6.Was würde folgen, wenn man für EIN NP-vollständiges Problem einen polynomiellen Algorithmus fände?
Antwort: dann wäre P = NP, also alle NP-Probleme effizient lösbar
Erklärung: Da jedes NP-Problem polynomiell auf ein NP-vollständiges reduzierbar ist, würde ein Polynomialalgorithmus für ein NP-vollständiges Problem alle NP-Probleme effizient lösbar machen, also P = NP. Das ist der Kern der offenen Frage.
Klausur-Quiz
Klausurfragen mit Lösungen (6)
- F1.Wie ist NP über Verifikation definiert?
Antwort: Probleme, deren Lösung in polynomieller Zeit verifizierbar ist (Zertifikat)
Erklärung: NP ist die Klasse der Probleme, für die es ein in polynomieller Zeit prüfbares Zertifikat (eine vorgeschlagene Lösung) gibt. Äquivalent: eine nichtdeterministische TM löst sie in polynomieller Zeit.
- F2.Welche Inklusionskette ist korrekt (und bekannt)?
Antwort: `P ⊆ NP ⊆ PSPACE ⊆ EXPTIME`
Erklärung: Es gilt `P ⊆ NP ⊆ PSPACE ⊆ EXPTIME`. Zusätzlich ist bewiesen `P subsetneq EXPTIME`, es gibt also nachweislich Probleme außerhalb von P.
- F3.Ordne jeden Begriff der richtigen Aussage zu.
Zuordnungen:
- P → in polynomieller Zeit lösbar
- NP → in polynomieller Zeit verifizierbar
- NP-schwer → mindestens so schwer wie alles in NP
- NP-vollständig → NP-schwer UND in NP
Erklärung: P = lösbar, NP = verifizierbar, NP-schwer = untere Schranke (alle NP reduzierbar), NP-vollständig = NP-schwer und selbst in NP.
Typ: Zuordnung
- F4.Ein Problem ist NP-vollständig, wenn es {{1}} ist und zugleich {{2}}. Das erste so bewiesene Problem war {{3}} (Cook-Levin 1971).
Lösungen pro Lücke:
- {{1}}: in NP / NP
- {{2}}: NP-schwer / NP-hart
- {{3}}: SAT / Erfüllbarkeit / Erfuellbarkeit
Erklärung: NP-vollständig = in NP UND NP-schwer. SAT war das erste per Cook-Levin als NP-vollständig bewiesene Problem.
Typ: Lückentext
- F5.P = NP ist mathematisch bewiesen.
Antwort: Falsch
Erklärung: Falsch. Ob `P = NP` gilt, ist offen und eines der sieben Millennium-Probleme. Die meisten Fachleute vermuten `P ≠ NP`, ein Beweis steht aber aus.
Typ: Wahr/Falsch
- F6.Warum ist das Halteproblem NP-schwer, aber NICHT NP-vollständig?
Antwort: weil es zwar mindestens so schwer wie alle NP-Probleme, aber selbst nicht in NP ist (es ist sogar unentscheidbar)
Erklärung: NP-vollständig verlangt beides: NP-schwer UND in NP. Das Halteproblem ist NP-schwer (man kann NP-Probleme darauf reduzieren), aber es ist unentscheidbar und liegt damit nicht in NP. Also NP-schwer, aber nicht NP-vollständig.
