Mit Google fortfahren
Beim Sudoku merkst du den Unterschied schnell: Eine fertige Lösung zu kontrollieren ist viel leichter, als sie selbst zu finden. Auch bei einem Zahlenschloss ist das ähnlich. Wenn dir jemand die Kombination nennt, testest du sie direkt. Ohne Hinweis musst du vielleicht sehr lange suchen.
- Du verstehst, was das P-NP-Problem fragt.
- Du unterscheidest zwischen Finden und Überprüfen.
- Du erklärst P und NP mit einfachen Beispielen.
- Du verstehst, warum NP-vollständige Probleme so wichtig sind.
Finden und Überprüfen
Ein Algorithmus ist eine genaue Schritt-für-Schritt-Anleitung, mit der ein Computer eine Aufgabe bearbeitet. Ein Problem meint hier eine ganze Aufgabenart, nicht nur eine einzelne Aufgabe. Zum Beispiel: „Sortiere eine Liste“ oder „Gibt es einen gültigen Weg durch diese Städte?“
Ein Entscheidungsproblem ist ein Problem, bei dem die Antwort nur Ja oder Nein lautet.
Beispiel: „Gibt es für dieses Sudoku mindestens eine gültige Lösung?“
Beim P-NP-Problem betrachtet man vor allem Entscheidungsprobleme. So kann man Aufgaben besser vergleichen. Aus „Finde den besten Weg“ wird zum Beispiel: „Gibt es einen Weg, der alle Bedingungen erfüllt?“
Sudoku als Entscheidungsproblem:
Frage: „Gibt es eine gültige Lösung für dieses Sudoku?“
Wenn dir jemand ein fertig ausgefülltes Sudoku zeigt, prüfst du Zeilen, Spalten und Kästchen. Das ist überschaubar.
Eine Lösung selbst zu finden, kann viel mehr Sucharbeit brauchen.
Der wichtigste Unterschied lautet: Eine Lösung finden ist nicht dasselbe wie eine Lösung überprüfen.
Interaktive Quizfrage wird geladen ...
Was bedeutet schnell?
Im Alltag heißt „schnell“ vielleicht: wenige Sekunden. In der theoretischen Informatik fragt man anders: Wie stark wächst die Arbeit, wenn die Eingabe größer wird?
Die Eingabegröße ist die Größe der Daten, die ein Algorithmus bekommt. Bei einer Liste ist das oft die Anzahl der Einträge. Bei einem Verkehrsnetz kann es die Anzahl der Orte und Verbindungen sein.
Die Laufzeit beschreibt, wie viele Rechenschritte ein Algorithmus ungefähr braucht. Gemeint ist nicht die genaue Zeit auf deinem Laptop, sondern das Wachstum bei größeren Aufgaben.
Polynomialzeit bedeutet: Die Laufzeit wächst höchstens wie eine Potenz der Eingabegröße, zum Beispiel wie \(n\), \(n^2\) oder \(n^3\).
Dabei steht \(n\) für die Eingabegröße.
Polynomialzeit gilt in der Komplexitätstheorie als effizient. Das heißt nicht, dass jeder solche Algorithmus in der Praxis sofort fertig ist. Aber das Wachstum bleibt besser kontrollierbar als bei reinem Durchprobieren sehr vieler Möglichkeiten.
Du sortierst Karteikarten nach Namen.
Bei 10 Karten geht das schnell. Bei 100 Karten dauert es länger. Ein guter Sortieralgorithmus wächst aber nicht völlig unkontrolliert.
Darum gehört Sortieren zu den effizient lösbaren Aufgabenarten.
Du probierst ein Zahlenschloss ohne Hinweis.
Bei 3 Stellen gibt es 1000 Möglichkeiten. Bei 6 Stellen gibt es 1000000 Möglichkeiten. Jede zusätzliche Stelle vergrößert die Suche stark.
Das zeigt: Blindes Ausprobieren kann sehr schnell unpraktisch werden.
„Schnell“ heißt hier: Die Arbeit wächst mit der Eingabegröße noch kontrollierbar.
Interaktiver Lückentext wird geladen ...
Die Klasse P
Jetzt kannst du die erste wichtige Klasse verstehen. Eine Komplexitätsklasse ist eine Gruppe von Problemen, die nach ihrer Schwierigkeit zusammengefasst werden.
P ist die Klasse der Entscheidungsprobleme, die ein Computer in Polynomialzeit lösen kann.
Wenn ein Problem in P liegt, gibt es also einen effizienten Algorithmus, der für jede Eingabe die richtige Ja-oder-Nein-Antwort findet.
Problem: „Kommt der Name Lea in dieser sortierten Liste vor?“
Ein Suchalgorithmus kann die Liste geschickt durchsuchen. Er muss nicht jeden möglichen Namen der Welt ausprobieren.
Diese Aufgabenart ist effizient lösbar.
Problem: „Ist diese Zahl gerade?“
Der Algorithmus prüft, ob die Zahl durch 2 teilbar ist. Das geht auch bei großen Zahlen nach einem klaren Verfahren.
Dieses Entscheidungsproblem liegt in P.
P bedeutet: Der Computer kann die Antwort selbst effizient finden.
Interaktive Quizfrage wird geladen ...
Die Klasse NP
Bei vielen Aufgaben ist das Überprüfen einfacher als das Finden. Genau hier kommt NP ins Spiel.
NP ist die Klasse der Entscheidungsprobleme, bei denen man eine vorgeschlagene Ja-Lösung in Polynomialzeit überprüfen kann.
Eine vorgeschlagene Lösung ist ein Kandidat, den jemand als Beweis für Ja vorlegt. Beim Sudoku ist das ein fertig ausgefülltes Gitter. Beim Zahlenschloss ist es eine Kombination wie 8256. Beim Städteweg ist es eine Reihenfolge der Städte.
Wichtig: NP heißt nicht „nicht polynomiell“. Das ist ein häufiger Fehler. NP bedeutet hier: Eine Ja-Lösung kann schnell geprüft werden, wenn sie vorliegt.
Problem: „Gibt es einen Weg durch diese Städte, der jede Stadt genau einmal besucht?“
Vorgeschlagene Ja-Lösung: Eine Liste der Städte in einer bestimmten Reihenfolge.
Prüfung: Du kontrollierst, ob jede Stadt genau einmal vorkommt und ob die angegebenen Verbindungen existieren. Das ist direkter, als alle möglichen Reihenfolgen selbst zu suchen.
Problem: „Hat diese Zahl einen Teiler zwischen 2 und 1000?“
Vorgeschlagene Ja-Lösung: Eine konkrete Zahl, zum Beispiel 37.
Prüfung: Du teilst und schaust, ob kein Rest bleibt und ob der Teiler im erlaubten Bereich liegt. Das Prüfen dieses Kandidaten ist viel einfacher als planloses Suchen.
Bei NP geht es besonders um Ja-Antworten. Ein passender Kandidat kann Ja schnell belegen. Für Nein gibt es oft keinen genauso kurzen Beleg, weil man dann zeigen müsste, dass kein Kandidat funktioniert.
NP bedeutet: Wenn dir jemand eine passende Ja-Lösung gibt, kannst du sie effizient prüfen.
Interaktiver Lückentext wird geladen ...
Interaktive Quizfrage wird geladen ...
Die offene Frage
Jetzt kommt das eigentliche Rätsel. Wir wissen: Jedes Problem aus P liegt auch in NP. Denn wenn ein Computer die Antwort schnell finden kann, kann man eine passende Ja-Lösung auch schnell prüfen.
Unbekannt ist die andere Richtung. Vielleicht ist jedes schnell prüfbare Problem auch schnell lösbar. Dann wäre \(P = NP\). Vielleicht gibt es aber Probleme, deren Lösungen man schnell prüfen kann, die man grundsätzlich nicht schnell finden kann. Dann wäre \(P \ne NP\).
Das P-NP-Problem fragt: Sind alle schnell prüfbaren Entscheidungsprobleme auch schnell lösbar?
Bisher kennt niemand einen Beweis. Viele Fachleute vermuten, dass \(P \ne NP\) gilt. Aber eine Vermutung ist noch kein Beweis.
Zahlenschloss:
Prüfen: Du stellst 8256 ein und schaust, ob es aufgeht.
Finden: Ohne Hinweis musst du viele Kombinationen testen.
Das Beispiel beweist nicht \(P \ne NP\). Es zeigt nur die Denkweise: Prüfen kann viel leichter wirken als Finden.
Routenplanung:
Prüfen: Eine vorgeschlagene Route erfüllt alle Bedingungen.
Finden: Du musst aus sehr vielen möglichen Routen eine passende auswählen.
Wichtig ist nicht eine kleine Karte, sondern das Wachstum bei immer größeren Eingaben.
Das P-NP-Problem gehört zu den bekanntesten offenen Problemen der Informatik und Mathematik. Das Clay Mathematics Institute zählt es zu den Millennium-Problemen.
\(P = NP\) würde bedeuten: Schnell prüfbar reicht immer aus, um auch schnell lösbar zu sein. \(P \ne NP\) würde bedeuten: Manche Probleme bleiben beim Finden viel schwerer als beim Prüfen.
Interaktive Quizfrage wird geladen ...
NP-vollständig
Einige Probleme in NP sind besonders zentral. Sie sind wie Knotenpunkte: Wenn man eines davon effizient lösen könnte, hätte das Folgen für alle Probleme in NP.
Dafür brauchst du zwei Begriffe. Eine Reduktion ist eine effiziente Umformung von einem Problem in ein anderes. Sie zeigt: Wenn ich das zweite Problem lösen kann, kann ich damit auch das erste lösen.
Ein Problem heißt NP-schwer, wenn jedes Problem aus NP in Polynomialzeit auf dieses Problem zurückgeführt werden kann.
Ein Problem heißt NP-vollständig, wenn es in NP liegt und zusätzlich NP-schwer ist.
NP-vollständige Probleme sind also schnell prüfbar und zugleich mindestens so schwer wie alle anderen Probleme in NP. Deshalb sind sie für das P-NP-Problem so wichtig.
Rucksackproblem als Entscheidungsproblem:
Du hast Gegenstände mit Gewicht und Wert. Die Frage lautet: „Gibt es eine Auswahl, die in den Rucksack passt und mindestens einen bestimmten Wert erreicht?“
Prüfen: Eine vorgeschlagene Auswahl lässt sich addieren. Du kontrollierst Gewicht und Wert.
Finden: Eine passende Auswahl kann schwierig sein, weil sehr viele Kombinationen möglich sind.
Erfüllbarkeit von Aussagenlogik:
Du hast eine logische Formel mit Variablen, die wahr oder falsch sein können. Die Frage lautet: „Gibt es eine Belegung, die die ganze Formel wahr macht?“
Prüfen: Eine vorgeschlagene Belegung setzt du ein und rechnest die Formel aus.
Finden: Eine passende Belegung zu entdecken, kann sehr schwer sein.
Wenn nur ein einziges NP-vollständiges Problem effizient gelöst würde, dann wäre \(P = NP\) bewiesen.
Interaktive Mindmap wird geladen ...
Interaktive Quizfrage wird geladen ...
Zusammenfassung
Das P-NP-Problem fragt, ob jedes Problem, dessen Ja-Lösung schnell geprüft werden kann, auch schnell gelöst werden kann. Die Klasse P enthält Entscheidungsprobleme, die in Polynomialzeit lösbar sind. Die Klasse NP enthält Entscheidungsprobleme, bei denen eine vorgeschlagene Ja-Lösung in Polynomialzeit prüfbar ist.
P liegt sicher in NP. Unbekannt ist, ob auch jedes NP-Problem in P liegt. Genau das meint die Frage \(P = NP\).
Interaktive Lernkarten wird geladen ...
Kurz gesagt: P fragt nach schnellem Finden. NP fragt nach schnellem Prüfen. Das P-NP-Problem fragt, ob beides am Ende gleich mächtig ist.