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).
Teil 1·Erklärung
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
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).
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:
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)".
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
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 ⊆ NP ⊆ PSPACE ⊆ EXPTIMEP 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 (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 (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).
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.
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.
P = NP ist ein Millennium-Problem (1 Mio. Dollar Preisgeld) und gilt als wahrscheinlich falsch (P ≠ NP), aber unbewiesen. Praktische Konsequenzen:
P ≠ NP ist die Hoffnung dahinter.Die bekannte Hierarchie: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME, und bewiesen ist P subsetneq EXPTIME (es gibt also nachweislich nicht effizient lösbare Probleme).
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.
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.
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)".
Klausurfragen mit Lösungen (6)
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.
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.
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
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.
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.
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.
Klausurfragen mit Lösungen (6)
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.
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.
Zuordnungen:
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
Lösungen pro Lücke:
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
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
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.