Dual-Mode Comparison

P vs NP ist eines der bedeutendsten offenen Probleme der Informatik. P-Probleme sind Probleme, deren Lösung schnell überprüft werden kann. NP-Probleme sind Probleme, bei denen man eine vorgeschlagene Lösung schnell verifizieren kann. Beispiel: Sudoku. Eine Lösung zu überprüfen ist schnell (P), aber eine zu finden ist schwer. Die große Frage: Ist P = NP? Wenn ja, würde bedeuten: Was schnell überprüfbar ist, ist auch schnell lösbar. Das würde Kryptographie zusammenbrechen lassen!

Das P vs NP Problem ist eines der sieben Millennium Prize Problems der Clay Mathematics Institute. **Def: P** P sind Entscheidungsprobleme, für die eine Lösung in polynomialer Zeit (Turing-Maschine) berechenbar ist. **Def: NP** NP sind Probleme, für die eine gegebene Lösung in polynomialer Zeit *verifizierbar* ist. **Klarstellung: Nicht dasselbe!** - Lösen ist schwerer als verifizieren - Jedes P-Problem ist auch NP - Aber ist jedes NP-Problem auch P? **Beispiele:** - Faktorisierung: NP (überprüfbar), aber P? Unbekannt - SAT (Satisfiability): NP-vollständig - Reisendenproblem: NP (verifizierbar), nicht bekannt als P **Wenn P ≠ NP:** - Die meisten kryptographischen Systeme bleiben sicher - RSA-Verschlüsselung funktioniert **Wenn P = NP:** - Alle modernen Kryptographie bricht zusammen - Beliebige NP-Probleme werden effizient lösbar - Theoretische Informatik wird revolutioniert