Computational complexity - Cheatsheet

Definitionen und Eigenschaften der Klasse P

Definition:

Klasse P umfasst alle Entscheidungsprobleme, die von einer deterministischen Turingmaschine in polynomialer Zeit gelöst werden können.

Details:

• Ein Problem gehört zur Klasse P, wenn es eine Turingmaschine gibt, die das Problem in Laufzeit O(n^k) für ein konstantes k löst.
• Polynomielle Zeitkomplexität: T(n) = O(n^k) wobei T(n) die Laufzeit und n die Eingabegröße ist.
• Wichtige Eigenschaft: Alle Algorithmen, die ein Problem der Klasse P lösen, sind effizient bzw. praktisch lösbar.

Das Problem der NP-Vollständigkeit

Definition:

NP-vollständige Probleme sind diejenigen Entscheidungsprobleme, die sowohl in NP liegen als auch NP-schwer sind.

Details:

• Ein Problem A ist in NP, wenn eine Lösung in polynomieller Zeit verifiziert werden kann.
• Ein Problem A ist NP-schwer, wenn jedes Problem in NP auf A in polynomieller Zeit reduzierbar ist.
• Falls ein NP-vollständiges Problem in polynomieller Zeit lösbar ist, sind alle Probleme in NP polynomiell lösbar.
• Das berühmte Beispiel ist das SAT-Problem.

Polynomzeit-Reduktionen

Definition:

Polynomzeit-Reduktionen, auch bekannt als polynomielle Reduktionen, sind Transformationen eines Problems in ein anderes, wobei die Umwandlung durch ein Algorithmus erfolgt, der in polynomieller Zeit läuft.

Details:

• Nützlich zur Klassifizierung von Problemen basierend auf ihrer Schwierigkeit.
• Formell: Ein Problem A ist polynomzeit-reduzierbar auf ein Problem B (A ≤P B), wenn es eine Funktion f gibt, die A auf B in polynomieller Zeit transformiert.
• Mathematisch ausgedrückt: A ≤P B ⇔ ∃ f: {0,1}* → {0,1}* und f ist in P, so dass für alle x gilt: x ∈ A ⇔ f(x) ∈ B
• Wichtig für die Theorie der NP-Vollständigkeit: Ein Problem ist NP-vollständig, wenn es in NP liegt und jedes andere Problem in NP in polynomieller Zeit auf es reduzierbar ist.

Log-Raum-Reduktionen

Definition:

Log-Raum-Reduktionen sind Reduktionen zwischen Problemen, die mit logarithmischem Platz (Log-Space) berechnet werden können.

Details:

• Verwendet eine log-space transducer, die den Eingabestrang liest und den Ausgabestrang schreibt, während nur O(log n) Speicherplatz verwendet wird.
• Formal: Ein Problem A log-raum-reduziert auf Problem B (A ≤log B), wenn es eine log-space Turingmaschine gibt, die eine Eingabe x in eine Eingabe y für B umwandelt, so dass x in A ist genau dann, wenn y in B ist.
• Viel genutzt in der Komplexitätstheorie zur Charakterisierung von Komplexitätsklassen wie L, NL, P.
• Ermöglicht die Untersuchung der Schwierigkeit von Problemen unter Speicherbeschränkungen.
• Beispiel: Überprüfung der Erreichbarkeit in gerichteten Graphen ist NL-vollständig unter log-raum-Reduktion.

Hierarchiesätze in der Komplexitätstheorie

Definition:

Hierarchiesätze zeigen, dass mehr Ressourcen (z.B. Zeit oder Platz) mehr Problemlösungsmöglichkeiten schaffen.

Details:

• Zeit-Hierarchiesatz: \( TIME(f(n)) \subsetneq TIME(g(n)) \) für \( f(n) = o(g(n)) \)
• Platz-Hierarchiesatz: \( SPACE(f(n)) \subsetneq SPACE(g(n)) \) für \( f(n) = o(g(n)) \)
• Unterscheidung in deterministisch und nicht-deterministisch
• Wichtige Implikation: P ≠ PSPACE

Dynamische Programmierung

Definition:

Optimierungstechnik zur Lösung komplexer Probleme durch Zerlegung in einfachere Teilprobleme und Speicherung der Lösungen dieser Teilprobleme, um Redundanzen zu vermeiden.

Details:

• Grundidee: Probleme in Teilprobleme zerlegen
• Speichere Zwischenergebnisse zur Wiederverwendung
• Zwei Hauptansätze: Top-Down (Memoisierung) und Bottom-Up
• Verwendet bei Problemen mit überlappenden Teilproblemen und optimaler Substruktur
• Zeitkomplexität in der Regel deutlich besser als naive Rekursion
• Anwendungen: Fibonacci-Zahlen, Kürzeste Pfade, Rucksackproblem, usw.
• Komplexitätsanalyse oft abhängig von Anzahl der Teilprobleme und Aufwand zum Lösen eines Teilproblems

Branch-and-Bound-Techniken

Definition:

Branch-and-Bound ist eine algorithmische Methode zur Lösung kombinatorischer Optimierungsprobleme durch sukzessives Aufteilen des Suchraums und Verwerfen unvorteilhafter Lösungskandidaten.

Details:

• Nutzen Begrenzungen, um Teillösungen (Zweige) zu verwerfen.
• Teile-und-Herrsche-Ansatz: Problem in Teilprobleme aufspalten (branching).
• Obere und untere Schranken berechnen, um Suchbereich einzugrenzen (bounding).
• Wichtig bei NP-schweren Problemen zur Reduktion der Berechnungszeit.
• Typische Anwendungen: TSP, Rucksackproblem, Integer-Programmierung.

Polynomialzeit-Approximationsschemata (PTAS)

Definition:

Algorithmische Technik zur näherungsweisen Lösung von NP-schweren Problemen in Polynomialzeit.

Details:

• Für jeden \(\text{ε} > 0\) existiert ein Algorithmus der in Polynomialzeit ein \(1 + \text{ε}\)-Approximation liefert.
• Laufzeit des Algorithmus hängt polynomiell von der Eingabegröße \(n\) und exponentiell von \(\frac{1}{\text{ε}}\) ab: \(O(n^{f(1/\text{ε})})\).
• Beispiele: Knapsack-Problem, Euclidean Traveling Salesman Problem (Euclid. TSP).