| Typ | Konzept |
|---|---|
| Quellen | Quelle - Automatentheorie Zusammenfassung Quelle - Recherche - BWL Nachprüfung und Heuristiken 2026 Quelle - Neuronale Netze selbst programmieren |
| Erstellt | 2026-09-24 |
| Aktualisiert | 2026-09-26 |
| Tags | theoretische-informatik, komplexität, algorithmen |
Untersucht, wie viel Zeit und Speicher lösbare Probleme benötigen. Sie teilt Probleme mit der O-Notation in Klassen ein. Die zentrale offene Frage ist P vs. NP.
Grundgedanke
Prinzipiell lösbar (entscheidbar → Berechenbarkeit) heisst nicht praktisch lösbar, wenn die Laufzeit für realistische Eingaben zu lang wird (Quelle - Automatentheorie Zusammenfassung).
O-Notation und Laufzeiten
| Ordnung | Name | praktisch? |
|---|---|---|
| O(1) | konstant | ja |
| O(log n) | logarithmisch | ja |
| O(n) | linear | ja |
| O(n log n) | n-log-n | ja (z.B. Heapsort) |
| O(n²), O(n³) | quadratisch, kubisch | ja |
| O(nᵏ), k ≥ 4 | polynomiell | schon sehr gross |
| O(c^(nᵏ)), c > 1, z.B. O(2ⁿ) | exponentiell | inakzeptabel |
- Untere Schranke: Mindestaufwand, den jeder Algorithmus für ein Problem braucht. Ein Algorithmus ist optimal, wenn er sie erreicht. Beispiel: Vergleichsbasiertes Sortieren braucht Ω(n log n), Heapsort erreicht das.
- Obere Schranke: Garantie, dass das Problem mit gegebenen Ressourcen lösbar ist (durch einen konkreten Algorithmus).
P und NP
- P: Probleme, die eine deterministische Turingmaschine in Polynomzeit löst.
- NP: Probleme, die eine nichtdeterministische Turingmaschine in Polynomzeit löst. Gleichwertig: Eine vorgeschlagene Lösung lässt sich in Polynomzeit prüfen.
- Die Umwandlung nichtdeterministisch → deterministisch kostet (nach heutigem Wissen) exponentielle Zeit.
- NP-vollständig: ein Problem in NP, auf das sich alle NP-Probleme polynomiell reduzieren lassen. Liegt ein einziges davon in P, dann gilt P = NP.
- P = NP? ist offen. Allgemein wird P ≠ NP angenommen (Quelle - Automatentheorie Zusammenfassung).
NP-vollständige Probleme in der Praxis
Bin Packing, Rucksack, Travelling Salesman, Scheduling (Arbeitsvorbereitung, Transport, Betriebssysteme, Stundenpläne). Gelöst werden sie „zufriedenstellend“ mit Heuristiken, suboptimalen und probabilistischen Verfahren.
Belegt ist das für die Ablaufplanung in der Fertigung: Den kürzesten Plan zu finden ist im Flow Shop ab 3 Maschinen und im Job Shop ab 2 Maschinen NP-vollständig (Garey, Johnson, Sethi 1976). Mit 2 Maschinen im Flow Shop löst die Johnson-Regel das Problem dagegen exakt und schnell. Für grosse Probleme gibt es Metaheuristiken: genetische Algorithmen (Holland 1975), Simulated Annealing (Kirkpatrick u.a. 1983), Tabu-Suche (Glover 1986) (Quelle - Recherche - BWL Nachprüfung und Heuristiken 2026). Vergleich mit der BWL in Heuristiken in BWL und Informatik.
Die Übersicht der Komplexitätsklassen auf S. 50 der Quelle (konstant, logarithmisch, linear, n-log-n, polynomiell O(nᵏ) mit k ≥ 2, exponentiell O(dⁿ) mit d > 1) stimmt mit der Tabelle oben überein. Die Suchstrategien aus der wissensbasierten Bildanalyse (Bergsteigen, Strahlensuche, A*) sind Beispiele für solche Heuristiken gegen kombinatorische Explosion. Die P-vs-NP-Frage ist auch 2026 ungelöst (Millennium-Problem).
Verwandt
- Berechenbarkeit – die Frage davor: überhaupt lösbar?
- Turingmaschine – das Maschinenmodell für P und NP
- Wissensbasierte Bildanalyse – heuristische Suche in der Praxis
- Heuristiken in BWL und Informatik – Heuristiken für Marketing-Mix und Produktionsplanung
- Produktionsplanung und -steuerung – Ablaufplanung als NP-schweres Praxisproblem
- Verschlüsselung – Kryptographie nutzt Schwierigkeit gezielt: RSA ist nur sicher, solange Faktorisieren nicht effizient geht
- Kombinatorik – n!, 2ⁿ und kⁿ: woher die exponentiellen Zahlen kommen
- Potenz, Wurzel und Logarithmus – logarithmische und exponentielle Laufzeiten
- Gradientenverfahren – warum man Gewichte nicht durchprobieren kann: 1000¹⁸ Kombinationen schon bei 18 Gewichten