Komplexität und praktische Grenzen

Erklärung: Exponentiell heißt multiplikativ — jedes weitere Element verdoppelt die Arbeit. Von n = 50 auf n = 60 wächst die Zeit um den Faktor 2¹⁰ ≈ 1000.

Erklärung: Falsch — Faktor 1000 ≈ 2¹⁰ schafft bei O(2ⁿ) nur etwa zehn zusätzliche Elemente. Gegen exponentielles Wachstum hilft bessere Hardware fast nichts; es braucht bessere Algorithmen oder Abstriche.

Erklärung: Jede zusätzliche Stelle multipliziert die Möglichkeiten mit 26 — deshalb macht Länge Passwörter so viel stärker als Sonderzeichen allein.

Erklärung: Die Tourenzahl wächst fakultätsartig: bei n Städten (n − 1)!/2 Touren. 25 Städte ergeben 24!/2 ≈ 3 · 10²³ Touren — bei einer Milliarde Touren pro Sekunde rund 10 Millionen Jahre. (Bei 20 Städten wären es noch knapp 2 Jahre.) Das Problem ist lösbar, aber das vollständige Durchprobieren ist praktisch aussichtslos.

Erklärung: Polynomiell (n, n², n³ …) wächst zahm genug, dass größere Eingaben beherrschbar bleiben — die praktische Trennlinie zu exponentiell.

Erklärung: Beispiel Rundreise: Ob eine vorgelegte Tour kürzer als 500 km ist, prüft man im Nu — eine solche Tour zu FINDEN ist das Schwere. Prüfen leicht, Finden schwer: das ist NP.

Erklärung: Richtig — sie ist das berühmteste offene Problem der Informatik, mit einem Millionenpreis dotiert. Die meisten Fachleute vermuten P ≠ NP, bewiesen ist es nicht.

Erklärung: 128 Bit ergeben 2¹²⁸ ≈ 3,4 · 10³⁸ Schlüssel. Bei 10¹² pro Sekunde sind das ≈ 3,4 · 10²⁶ Sekunden, also rund 10¹⁹ Jahre — weit mehr als das Alter des Universums. Darauf ruht die Sicherheit: Mit Schlüssel ist die Rechnung leicht, ohne Schlüssel kennt man nur Verfahren, deren Aufwand mit der Schlüssellänge explodiert. Bewiesen ist diese Schwere nicht — die praktische Grenze wird zum Schutzschild.

Erklärung: Falsch — praktisch unlösbar heißt „lösbar, aber untragbar langsam"; unentscheidbar heißt „durch kein Programm lösbar, egal wie langsam". Zwei verschiedene Grenzen.

Erklärung: Der Standard-Umgang mit harten Problemen — Näherungsverfahren und Faustregeln liefern in Sekunden Lösungen, die nah am Optimum liegen.

Erklärung: Die Trennlinie der Komplexitätstheorie — polynomiell gilt als effizient, exponentiell als praktisch unbrauchbar für große Eingaben.

Erklärung: Jedes Element ist drin oder draußen — 2ⁿ Kombinationen. 2⁸⁰ ≈ 1,2 · 10²⁴: selbst bei einer Billion Fällen pro Sekunde rund 38 000 Jahre. (2⁶⁰ dagegen schafft so ein Rechner in knapp zwei Wochen.) Vollständiges Durchsuchen von Teilmengen ist der Prototyp exponentieller Verfahren.

Erklärung: Richtig — genau das ist die Definition von NP über das schnelle Prüfen vorgelegter Lösungen.

Erklärung: Schnelle Prüfbarkeit sichert NP-Mitgliedschaft. Ob ein schneller Lösungsalgorithmus existiert, ist gerade die offene P-NP-Frage.