P vs. NP-Problem

In der Komplexitätstheorie werden Probleme nach dem Aufwand klassifiziert, der zu ihrer Lösung nötig ist:

• P (Polynomial Time): Die Klasse aller Entscheidungsprobleme, die von einer deterministischen Turingmaschine in polynomieller Zeit gelöst werden können. Beispiel: Sortieren (O(n log n)), kürzester Weg (Dijkstra).
• NP (Nondeterministic Polynomial Time): Die Klasse aller Entscheidungsprobleme, deren Lösung in polynomieller Zeit verifiziert (nicht unbedingt gefunden!) werden kann. Gleichbedeutend: Lösbar von einer nichtdeterministischen TM in polynomieller Zeit.

Klar ist: P ⊆ NP (jedes effizient lösbare Problem ist auch effizient verifizierbar). Die große Frage: Gilt auch P = NP?

Der Kern des Unterschieds:

• Lösen (Finden): Eine Lösung von Grund auf berechnen. Für NP-Probleme kann dies exponentiell lange dauern.
• Verifizieren (Prüfen): Eine gegebene Lösung auf Korrektheit prüfen. Für NP-Probleme geht dies in polynomieller Zeit.

Beispiel Sudoku: Ein Sudoku zu lösen kann sehr aufwendig sein. Aber ein ausgefülltes Sudoku zu überprüfen (alle Regeln erfüllt?) geht schnell.

Ein Problem ist NP-vollständig, wenn:

1. Es in NP liegt (Lösung ist in polynomieller Zeit verifizierbar).
2. Jedes andere NP-Problem in polynomieller Zeit auf dieses Problem reduzierbar ist.

NP-vollständige Probleme sind die „schwersten“ Probleme in NP. Wenn für eines davon ein Polynomialzeit-Algorithmus gefunden würde, wäre P = NP bewiesen.

Das erste als NP-vollständig bewiesene Problem: SAT (Erfüllbarkeitsproblem der Aussagenlogik) – Satz von Cook (1971).

Eines der berühmtesten NP-vollständigen Probleme:

„Gegeben n Städte und die Entfernungen zwischen ihnen: Finde die kürzeste Rundreise, die jede Stadt genau einmal besucht und zum Ausgangspunkt zurückkehrt.“

Bei n Städten gibt es (n−1)!/2 mögliche Routen. Bei 20 Städten sind das über 60 Billionen Routen! Es gibt keinen bekannten Polynomialzeit-Algorithmus.

In der Praxis werden Heuristiken (z. B. Nearest-Neighbour, genetische Algorithmen) eingesetzt, die gute, aber nicht garantiert optimale Lösungen liefern.

Die Frage „P = NP?“ ist eines der sieben Millennium-Probleme des Clay Mathematics Institute (2000). Für die Lösung sind 1 Million US-Dollar Preisgeld ausgesetzt.

Die meisten Informatiker vermuten P ≠ NP, d. h. es gibt Probleme, die effizient verifizierbar, aber nicht effizient lösbar sind. Ein Beweis steht jedoch noch aus.

Auswirkungen, falls P = NP: Kryptographie wäre gebrochen (RSA basiert auf der Schwierigkeit der Faktorisierung). Viele Optimierungsprobleme wären effizient lösbar.

Abitur-Tipp: Im Abitur wird typischerweise gefragt: Was ist der Unterschied zwischen P und NP? Was bedeutet NP-Vollständigkeit? Erkläre am Beispiel des TSP. Präge dir ein: NP bedeutet nicht „nicht polynomiell“, sondern „nichtdeterministisch polynomiell“ (Lösung verifizierbar in Polynomialzeit). Das Sudoku-Beispiel eignet sich gut zur Veranschaulichung.