mirror of
https://github.com/theoleuthardt/hwr-notes.git
synced 2026-06-06 01:21:09 +00:00
397 lines
21 KiB
Markdown
397 lines
21 KiB
Markdown
# Komplexitätstheorie – Grundlagen, Entscheidbarkeit & Probleme
|
||
|
||
**Basierend auf:** KO1 & KO2 (Prof. Dr. Björn Grohmann, HWR Berlin)
|
||
|
||
-----
|
||
|
||
## 1. Die Turing-Maschine
|
||
|
||
### Was ist eine Turing-Maschine?
|
||
|
||
Eine Turing-Maschine (TM) ist ein abstraktes Berechnungsmodell – im Grunde der einfachste denkbare „Computer”. Sie besteht aus drei Teilen:
|
||
|
||
- **Ein unendlich langes Band**, unterteilt in Zellen. Jede Zelle enthält genau ein Symbol.
|
||
- **Ein Lese-/Schreibkopf**, der sich auf dem Band nach links oder rechts bewegen kann, Symbole lesen und schreiben kann.
|
||
- **Eine endliche Steuerung**, die anhand des aktuellen Zustands und des gelesenen Symbols entscheidet, was als nächstes passiert.
|
||
|
||
### Formale Definition
|
||
|
||
Eine TM ist ein 7-Tupel $(Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$:
|
||
|
||
|Bestandteil |Bedeutung |
|
||
|-------------------|------------------------------------------------------------------------------|
|
||
|$Q$ |Endliche Zustandsmenge |
|
||
|$\Sigma$ |Eingabealphabet (ohne Blanksymbol $\sqcup$) |
|
||
|$\Gamma$ |Bandalphabet ($\sqcup \in \Gamma$, $\Sigma \subseteq \Gamma$) |
|
||
|$\delta$ |Übergangsfunktion: $Q \times \Gamma \rightarrow Q \times \Gamma \times {L, R}$|
|
||
|$q_0$ |Startzustand |
|
||
|$q_{\text{accept}}$|Akzeptierzustand – die Maschine sagt „Ja” |
|
||
|$q_{\text{reject}}$|Ablehnungszustand – die Maschine sagt „Nein” |
|
||
|
||
Die Übergangsfunktion $\delta$ ist das Herzstück: Sie sagt „Wenn du im Zustand $q$ bist und Symbol $a$ liest, dann schreibe Symbol $b$, wechsle in Zustand $q’$ und bewege den Kopf nach links oder rechts.”
|
||
|
||
### Konfiguration
|
||
|
||
Eine Konfiguration ist eine Momentaufnahme der TM zu einem bestimmten Zeitpunkt. Sie umfasst den aktuellen Zustand, den Bandinhalt und die Kopfposition.
|
||
|
||
Beispiel: $1011q_701111$ bedeutet, dass auf dem Band „101101111” steht, die Maschine im Zustand $q_7$ ist und der Kopf auf dem Zeichen direkt rechts von $q_7$ steht (also auf der „0”).
|
||
|
||
### Was bedeutet „halten”?
|
||
|
||
Eine Turing-Maschine **hält**, wenn sie irgendwann in den Akzeptier- oder Ablehnungszustand gelangt und damit ihre Berechnung beendet. Wenn sie das nie tut, läuft sie endlos weiter – sie „hält nicht”. Das ist so, als würde ein Programm in einer Endlosschleife stecken und nie ein Ergebnis liefern.
|
||
|
||
-----
|
||
|
||
## 2. Varianten von Turing-Maschinen
|
||
|
||
### Mehrband-TM (Multitape TM)
|
||
|
||
Eine TM mit $k$ separaten Bändern und $k$ unabhängigen Köpfen. Die Übergangsfunktion hat die Form:
|
||
|
||
$$\delta: Q \times \Gamma^k \rightarrow Q \times \Gamma^k \times {L, R, S}^k$$
|
||
|
||
Jede Mehrband-TM kann durch eine Einband-TM simuliert werden (alle Bänder werden hintereinander auf ein Band geschrieben, getrennt durch #-Symbole). Die Simulation kostet quadratischen Zeitoverhead: $O(T(n)^2)$.
|
||
|
||
### Nichtdeterministische TM (NTM)
|
||
|
||
Die Übergangsfunktion liefert statt eines einzigen Nachfolgezustands eine **Menge** von möglichen Übergängen:
|
||
|
||
$$\delta: Q \times \Gamma \rightarrow \mathcal{P}(Q \times \Gamma \times {L, R})$$
|
||
|
||
Man kann sich das so vorstellen: An jedem Schritt „verzweigt” sich die Berechnung in mehrere parallele Pfade. Die NTM akzeptiert, wenn **mindestens ein** Pfad akzeptiert. Sie lehnt ab, wenn **alle** Pfade ablehnen.
|
||
|
||
Jede NTM kann durch eine deterministische TM simuliert werden, allerdings mit exponentiellem Zeitverlust: Eine $t(n)$-Zeit-NTM wird zu einer $2^{O(t(n))}$-Zeit-DTM.
|
||
|
||
### Universelle Turing-Maschine (UTM)
|
||
|
||
Eine UTM $\mathcal{U}$ kann jede andere TM simulieren. Sie bekommt als Eingabe die Beschreibung einer TM $M$ (kodiert als Bitfolge, die sogenannte **Gödelnummer**) und eine Eingabe $x$ und berechnet dann $M(x)$.
|
||
|
||
Die UTM ist im Grunde der theoretische Vorläufer des modernen Computers: Ein Gerät, das beliebige Programme ausführen kann.
|
||
|
||
-----
|
||
|
||
## 3. Äquivalente Berechnungsmodelle
|
||
|
||
Mehrere andere Berechnungsmodelle sind **genauso mächtig** wie die Turing-Maschine. Das stützt die Church-Turing-These.
|
||
|
||
|Modell |Kernidee |
|
||
|-------------------|---------------------------------------------------------------------------------------|
|
||
|**WHILE-Programme**|Schleifen mit Inkrement/Dekrement auf Variablen |
|
||
|**GOTO-Programme** |Nummerierte Anweisungen mit Sprungbefehlen |
|
||
|**Lambda-Kalkül** |Funktionsdefinition und -anwendung (Grundlage funktionaler Programmierung) |
|
||
|**Rule 110** |Eindimensionaler Zellularautomat – selbst dieses einfache System ist Turing-vollständig|
|
||
|
||
### Church-Turing-These
|
||
|
||
> „Jede effektiv berechenbare Funktion kann durch eine Turing-Maschine berechnet werden.”
|
||
|
||
Das ist keine bewiesene Aussage, sondern eine These. Sie besagt: Es gibt kein Berechnungsmodell, das mehr berechnen kann als eine TM. Bisher wurde kein Gegenbeispiel gefunden.
|
||
|
||
-----
|
||
|
||
## 4. Entscheidbarkeit
|
||
|
||
### Turing-erkennbar (semi-entscheidbar)
|
||
|
||
Eine Sprache $L$ ist **Turing-erkennbar**, wenn es eine TM gibt, die so arbeitet:
|
||
|
||
- Eingabe $w \in L$: Die TM akzeptiert (hält und sagt „Ja”).
|
||
- Eingabe $w \notin L$: Die TM lehnt ab **oder läuft endlos weiter**.
|
||
|
||
Das Problem: Man weiß nie, ob die Maschine noch rechnet oder ob sie in einer Endlosschleife steckt.
|
||
|
||
### Turing-entscheidbar (entscheidbar)
|
||
|
||
Eine Sprache $L$ ist **Turing-entscheidbar**, wenn es eine TM gibt, die so arbeitet:
|
||
|
||
- Eingabe $w \in L$: Die TM akzeptiert.
|
||
- Eingabe $w \notin L$: Die TM lehnt ab.
|
||
- **Die TM hält immer** – sie liefert auf jeder Eingabe eine definitive Antwort.
|
||
|
||
### Der Zusammenhang
|
||
|
||
Eine Sprache ist entscheidbar **genau dann, wenn** sie sowohl Turing-erkennbar als auch co-Turing-erkennbar ist. Die Idee: Man lässt zwei Maschinen parallel laufen – eine für $L$, eine für das Komplement $\overline{L}$. Eine von beiden wird irgendwann akzeptieren, und dann hat man die Antwort.
|
||
|
||
### Hierarchie der Berechenbarkeit
|
||
|
||
```
|
||
Entscheidbar ⊂ Semi-entscheidbar ⊂ Alle Sprachen
|
||
(TM hält immer) (TM hält für w ∈ L) (manche sind gar nicht berechenbar)
|
||
```
|
||
|
||
-----
|
||
|
||
## 5. Unentscheidbare Probleme
|
||
|
||
### Das Halteproblem ($HALT_{\text{TM}}$)
|
||
|
||
$$HALT_{\text{TM}} = {\langle M, w \rangle \mid M \text{ ist eine TM und } M \text{ hält auf Eingabe } w}$$
|
||
|
||
**Frage:** Kann man im Voraus entscheiden, ob ein beliebiges Programm auf einer beliebigen Eingabe irgendwann anhält oder ewig weiterläuft?
|
||
|
||
**Antwort:** Nein – das Halteproblem ist unentscheidbar.
|
||
|
||
### Die Akzeptanzsprache ($A_{\text{TM}}$)
|
||
|
||
$$A_{\text{TM}} = {\langle M, w \rangle \mid M \text{ ist eine TM und } M \text{ akzeptiert } w}$$
|
||
|
||
$A_{\text{TM}}$ ist semi-entscheidbar (man kann $M$ auf $w$ simulieren), aber **nicht entscheidbar**.
|
||
|
||
### Beweis durch Diagonalisierung
|
||
|
||
Der Beweis nutzt dieselbe Idee wie Cantors Diagonalisierung:
|
||
|
||
1. **Annahme:** Es gibt einen Entscheider $H$, der für jede TM $M$ und jede Eingabe $w$ korrekt entscheidet, ob $M$ die Eingabe $w$ akzeptiert.
|
||
2. **Konstruktion:** Baue eine „teuflische” Maschine $D$, die bei Eingabe $\langle M \rangle$ den Entscheider $H$ auf $\langle M, \langle M \rangle \rangle$ aufruft – also fragt „akzeptiert $M$ sich selbst?” – und dann **das Gegenteil tut**.
|
||
3. **Widerspruch:** Was passiert bei $D(\langle D \rangle)$?
|
||
- Falls $H$ sagt „$D$ akzeptiert sich selbst” → $D$ lehnt ab. Aber dann akzeptiert $D$ sich selbst nicht – Widerspruch zu dem, was $H$ gesagt hat.
|
||
- Falls $H$ sagt „$D$ akzeptiert sich selbst nicht” → $D$ akzeptiert. Aber dann akzeptiert $D$ sich selbst doch – wieder Widerspruch.
|
||
1. **Schlussfolgerung:** $H$ kann nicht existieren.
|
||
|
||
Man kann sich das auch als Tabelle vorstellen: Zeilen sind TMs, Spalten sind Eingaben, Einträge sind 0 (lehnt ab) oder 1 (akzeptiert). $D$ nimmt die Diagonale und invertiert sie – und kann daher in keiner Zeile der Tabelle vorkommen, obwohl $D$ selbst eine TM ist.
|
||
|
||
### Postsches Korrespondenzproblem (PCP)
|
||
|
||
**Gegeben:** Wortpaare $(x_1, y_1), \ldots, (x_k, y_k)$, dargestellt als Dominosteine mit Ober- und Unterseite.
|
||
|
||
**Gefragt:** Kann man eine Folge von Dominosteinen (mit Wiederholung) so aneinanderlegen, dass die obere und die untere Zeichenkette identisch sind?
|
||
|
||
Das PCP ist unentscheidbar, aber semi-entscheidbar (man kann systematisch alle Kombinationen durchprobieren).
|
||
|
||
### Hilberts 10. Problem
|
||
|
||
**Frage (1900):** Gibt es ein Verfahren, das für jede Polynomgleichung mit ganzzahligen Koeffizienten entscheidet, ob sie eine ganzzahlige Lösung hat?
|
||
|
||
**Antwort (Matijassewitsch, 1970):** Nein – unentscheidbar.
|
||
|
||
### Weitere unentscheidbare Probleme
|
||
|
||
|Problem |Frage |Semi-entscheidbar? |
|
||
|-----------------------------------|-----------------------------------------------|------------------------------|
|
||
|$E_{\text{TM}}$: Leerheitsproblem |Ist $L(M) = \emptyset$? |Nein (co-Turing-erkennbar) |
|
||
|$EQ_{\text{TM}}$: Äquivalenzproblem|Gilt $L(M_1) = L(M_2)$? |Nein |
|
||
|$REGULAR_{\text{TM}}$ |Ist $L(M)$ regulär? |Nein |
|
||
|$MIN_{\text{TM}}$ |Ist $M$ eine minimale TM? |Nicht einmal semi-entscheidbar|
|
||
|Erfüllbarkeit (Prädikatenlogik) |Ist ein prädikatenlogischer Ausdruck erfüllbar?|Ja, aber unentscheidbar |
|
||
|Gültigkeit (Prädikatenlogik) |Ist ein Ausdruck allgemeingültig? |Ja, aber unentscheidbar |
|
||
|
||
-----
|
||
|
||
## 6. Zeitkomplexität
|
||
|
||
### Laufzeit
|
||
|
||
Die Laufzeit (Running Time) einer deterministischen TM $M$ ist die Funktion $f(n)$, die angibt, wie viele Schritte $M$ **im schlimmsten Fall** auf einer Eingabe der Länge $n$ benötigt.
|
||
|
||
Bei einer nichtdeterministischen TM zählt man die maximale Schrittzahl über **alle Berechnungspfade** (auch die nicht-akzeptierenden).
|
||
|
||
### Zeitkonstruierbarkeit
|
||
|
||
Eine Funktion $t(n)$ heißt zeitkonstruierbar, wenn man den Wert $t(n)$ selbst in $O(t(n))$ Schritten berechnen kann. Beispiele: $n$, $n \log n$, $n^2$, $2^n$.
|
||
|
||
### Simulationskosten
|
||
|
||
|Transformation |Zeitoverhead |
|
||
|-----------------------------------------------------|----------------------------|
|
||
|Alphabetreduktion (auf ${0,1,\sqcup,\triangleright}$)|$O(\log |
|
||
|$k$ Bänder → 1 Band |$O(k \cdot T(n)^2)$ |
|
||
|NTM → DTM |$2^{O(T(n))}$ (exponentiell)|
|
||
|Bidirektional → Unidirektional |$O(T(n))$ |
|
||
|
||
-----
|
||
|
||
## 7. Komplexitätsklassen
|
||
|
||
### Die wichtigsten Klassen im Überblick
|
||
|
||
|Klasse |Definition |Intuition |Beispiele |
|
||
|-----------|--------------------------------|------------------------------------|--------------------------------------------|
|
||
|**P** |$\bigcup_k \text{TIME}(n^k)$ |Effizient lösbar |Sortieren, kürzeste Wege, Primzahltest (AKS)|
|
||
|**NP** |$\bigcup_k \text{NTIME}(n^k)$ |Lösung effizient überprüfbar |SAT, Hamiltonkreis, TSP, Knapsack |
|
||
|**co-NP** |Komplemente der NP-Sprachen |„Nein”-Antwort effizient überprüfbar|UNSAT, Tautologie |
|
||
|**PSPACE** |$\bigcup_k \text{SPACE}(n^k)$ |Polynomieller Speicher reicht |TQBF |
|
||
|**EXPTIME**|$\bigcup_k \text{TIME}(2^{n^k})$|Exponentielle Zeit |Generalisiertes Schach |
|
||
|
||
### Die Inklusionskette
|
||
|
||
$$P \subseteq NP \subseteq PSPACE = NPSPACE \subseteq EXPTIME$$
|
||
|
||
Die Gleichheit $PSPACE = NPSPACE$ folgt aus Savitch’s Theorem.
|
||
|
||
### P vs. NP – Die zentrale offene Frage
|
||
|
||
**P** = Probleme, die ein Computer effizient **lösen** kann.
|
||
**NP** = Probleme, deren Lösung ein Computer effizient **überprüfen** kann.
|
||
|
||
Die Frage „Ist P = NP?” fragt im Kern: Ist jedes Problem, dessen Lösung leicht zu überprüfen ist, auch leicht zu finden? Die meisten Informatiker vermuten Nein. Das Problem ist eines der sieben Millennium-Probleme (Preisgeld: 1 Million Dollar).
|
||
|
||
### Speicherkomplexität
|
||
|
||
$$\text{SPACE}(f(n)) = {L \mid L \text{ wird von einer det. TM in } O(f(n)) \text{ Speicher entschieden}}$$
|
||
|
||
$$\text{NSPACE}(f(n)) = {L \mid L \text{ wird von einer nichtdet. TM in } O(f(n)) \text{ Speicher entschieden}}$$
|
||
|
||
### Savitch’s Theorem
|
||
|
||
$$\text{NSPACE}(f(n)) \subseteq \text{SPACE}(f^2(n))$$
|
||
|
||
Nichtdeterministischer Speicher lässt sich deterministisch mit nur quadratischem Mehraufwand simulieren. Die Kernidee ist die CANYIELD-Prozedur: Um zu prüfen, ob Konfiguration $c_2$ von $c_1$ in $t$ Schritten erreichbar ist, probiert man alle möglichen Zwischenkonfigurationen $c_m$ und prüft rekursiv, ob $c_1 \to c_m$ in $t/2$ Schritten und $c_m \to c_2$ in $t/2$ Schritten möglich ist. Die Rekursionstiefe ist $O(\log t)$, jede Ebene braucht $O(f(n))$ Speicher, also insgesamt $O(f(n)^2)$.
|
||
|
||
-----
|
||
|
||
## 8. NP-Vollständigkeit
|
||
|
||
### Polynomialzeit-Reduktion
|
||
|
||
Eine Sprache $A$ ist polynomialzeit-reduzierbar auf $B$ (geschrieben $A \leq_P B$), wenn es eine in Polynomialzeit berechenbare Funktion $f$ gibt mit:
|
||
|
||
$$w \in A \iff f(w) \in B$$
|
||
|
||
Intuition: Wenn man $B$ lösen kann, kann man auch $A$ lösen – man wandelt einfach jede $A$-Instanz mittels $f$ in eine $B$-Instanz um. $B$ ist also **mindestens so schwer** wie $A$.
|
||
|
||
### Definition: NP-vollständig
|
||
|
||
Eine Sprache $B$ ist NP-vollständig, wenn:
|
||
|
||
1. $B \in NP$ (die Lösung ist effizient überprüfbar), **und**
|
||
2. $A \leq_P B$ für **jedes** $A \in NP$ (jedes NP-Problem lässt sich auf $B$ reduzieren).
|
||
|
||
Erfüllt $B$ nur Bedingung 2, heißt $B$ **NP-hard** (NP-schwer). NP-harte Probleme müssen nicht selbst in NP liegen.
|
||
|
||
$$\text{NP-vollständig} = NP \cap \text{NP-hard}$$
|
||
|
||
### Cook-Levin-Theorem (1971/1973)
|
||
|
||
**SAT ist NP-vollständig.** Das war der erste Beweis, dass überhaupt ein NP-vollständiges Problem existiert. Daraus folgt: Könnte man SAT in Polynomialzeit lösen, wäre $P = NP$.
|
||
|
||
### PSPACE-Vollständigkeit
|
||
|
||
Eine Sprache $B$ ist PSPACE-vollständig, wenn $B \in PSPACE$ und jedes $A \in PSPACE$ polynomiell auf $B$ reduzierbar ist.
|
||
|
||
**TQBF** (True Quantified Boolean Formula) ist PSPACE-vollständig. TQBF fragt, ob eine voll quantifizierte Boolesche Formel (mit $\forall$ und $\exists$) wahr ist. TQBF verallgemeinert SAT: Während SAT nur fragt „Gibt es eine erfüllende Belegung?” ($\exists$), erlaubt TQBF auch Allquantoren ($\forall$), was das Problem härter macht.
|
||
|
||
-----
|
||
|
||
## 9. Die wichtigsten NP-vollständigen Probleme
|
||
|
||
### SAT (Erfüllbarkeitsproblem)
|
||
|
||
**Eingabe:** Eine Boolesche Formel $\phi$ (z.B. $(x \lor \bar{y}) \land (\bar{x} \lor z)$).
|
||
**Frage:** Gibt es eine Belegung der Variablen mit wahr/falsch, sodass die Formel wahr wird?
|
||
**Zertifikat:** Die erfüllende Belegung selbst – man setzt die Werte ein und prüft.
|
||
|
||
### Hamiltonkreis
|
||
|
||
**Eingabe:** Ein ungerichteter Graph.
|
||
**Frage:** Gibt es einen Rundweg, der **jeden Knoten genau einmal** besucht und zum Startknoten zurückkehrt?
|
||
**Zertifikat:** Der Rundweg selbst – man prüft, ob er jeden Knoten genau einmal enthält.
|
||
|
||
Die NP-Vollständigkeit wird durch Reduktion von SAT bewiesen, wobei eine Formel in einen Graphen mit speziellen Gadgets übersetzt wird (Variablenpfade, XOR-Gadgets, OR-Gadgets, Kreuzungs-Gadgets).
|
||
|
||
### Traveling Salesman Problem (TSP)
|
||
|
||
**Eingabe:** Städte mit Entfernungen und ein Budget $k$.
|
||
**Frage:** Gibt es eine Rundreise durch alle Städte mit Gesamtlänge $\leq k$?
|
||
**Zertifikat:** Die Rundreise selbst.
|
||
|
||
### Knapsack (Rucksackproblem)
|
||
|
||
**Eingabe:** Gegenstände mit Gewichten und Werten, ein Rucksack mit Kapazität $W$ und ein Zielwert $V$.
|
||
**Frage:** Kann man Gegenstände so auswählen, dass das Gesamtgewicht $\leq W$ ist und der Gesamtwert $\geq V$?
|
||
**Zertifikat:** Die Auswahl der Gegenstände.
|
||
|
||
### Minesweeper
|
||
|
||
**Eingabe:** Ein teilweise aufgedecktes Minesweeper-Feld.
|
||
**Frage:** Gibt es eine konsistente Minenbelegung für die verdeckten Felder?
|
||
|
||
Die NP-Vollständigkeit wird gezeigt, indem man logische Schaltkreise (Drähte, NOT-Gates, AND-Gates) innerhalb eines Minesweeper-Spielfelds simuliert. Damit lässt sich jede SAT-Instanz als Minesweeper-Konfiguration kodieren.
|
||
|
||
### Karp’s Liste (1972)
|
||
|
||
Richard Karp bewies 1972, dass 21 Probleme NP-vollständig sind, alle durch Reduktionen ausgehend von SAT. Dazu gehören unter anderem Clique, Node Cover, Chromatic Number, Set Covering, Exact Cover, 3D-Matching, Partition und Max Cut.
|
||
|
||
-----
|
||
|
||
## 10. NP-Härte von Videospielen
|
||
|
||
Viele Videospiele sind NP-hard. Dafür gibt es allgemeine Metatheorems:
|
||
|
||
### Metatheorem 1: Location Traversal + Single-Use Paths
|
||
|
||
Wenn ein Spiel bestimmte Punkte vorschreibt, die besucht werden müssen, und Wege nur einmal benutzbar sind, ist es NP-hard (Reduktion vom Hamiltonkreisproblem).
|
||
|
||
### Metatheorem 2: Tokens, Toll Roads, Location Traversal
|
||
|
||
Ein Spiel ist NP-hard, wenn es sammelbare Tokens, kostenpflichtige Wege und zu besuchende Orte hat. Beispiel: In Pac-Man sind Power Pills die Tokens und Geisterkorridore die Toll Roads.
|
||
|
||
### Metatheorem 3: Keys, Doors, One-Way Paths
|
||
|
||
Wie Metatheorem 2, aber mit Schlüsseln statt Tokens und Türen statt Toll Roads.
|
||
|
||
### Metatheorem 4: Doors + Pressure Plates
|
||
|
||
Türen und Druckplatten (die Türen öffnen/schließen) machen ein Spiel NP-hard, selbst wenn keine zwei Druckplatten dieselbe Tür steuern.
|
||
|
||
### Metatheorem 5: Doors + k-Buttons
|
||
|
||
Buttons, bei denen der Spieler entscheiden kann, ob er sie drückt, und die $k$ Türen gleichzeitig beeinflussen, machen ein Spiel NP-hard für $k \geq 2$.
|
||
|
||
-----
|
||
|
||
## 11. Zusammenfassung: Was ist wo?
|
||
|
||
### Entscheidbarkeit
|
||
|
||
|Problem |Entscheidbar?|Semi-entscheidbar? |
|
||
|------------------------------------------|-------------|--------------------------|
|
||
|$A_{\text{TM}}$ (akzeptiert M w?) |Nein |Ja |
|
||
|$HALT_{\text{TM}}$ (hält M auf w?) |Nein |Ja |
|
||
|PCP |Nein |Ja |
|
||
|Hilberts 10. Problem |Nein |Ja |
|
||
|$E_{\text{TM}}$ (ist $L(M)$ leer?) |Nein |Nein (co-Turing-erkennbar)|
|
||
|$EQ_{\text{TM}}$ (sind $L(M_1) = L(M_2)$?)|Nein |Nein |
|
||
|$MIN_{\text{TM}}$ (ist M minimal?) |Nein |Nein |
|
||
|
||
### Komplexität
|
||
|
||
|Problem |Klasse |
|
||
|------------------------|------------------|
|
||
|Sortieren, kürzeste Wege|P |
|
||
|Primzahltest (AKS) |P |
|
||
|SAT |NP-vollständig |
|
||
|Hamiltonkreis |NP-vollständig |
|
||
|TSP |NP-vollständig |
|
||
|Knapsack |NP-vollständig |
|
||
|Minesweeper |NP-vollständig |
|
||
|TQBF |PSPACE-vollständig|
|
||
|Generalisiertes Schach |EXPTIME |
|
||
|
||
### Beziehungen zwischen den Klassen
|
||
|
||
```
|
||
Entscheidbar: P ⊆ NP ⊆ PSPACE = NPSPACE ⊆ EXPTIME
|
||
|
||
Unentscheidbar: Halteproblem, A_TM, PCP, Hilberts 10. Problem, ...
|
||
```
|
||
|
||
-----
|
||
|
||
## 12. Glossar
|
||
|
||
| Begriff | Bedeutung |
|
||
| ---------------------------- | ------------------------------------------------------------ |
|
||
| **Turing-Maschine** | Abstraktes Berechnungsmodell mit Band, Kopf und Steuerung |
|
||
| **Konfiguration** | Momentaufnahme: Zustand + Band + Kopfposition |
|
||
| **Gödelnummer** | Binäre Kodierung einer TM |
|
||
| **Church-Turing-These** | Alles Berechenbare ist Turing-berechenbar |
|
||
| **Turing-erkennbar** | TM akzeptiert $w \in L$, kann auf $w \notin L$ endlos laufen |
|
||
| **Turing-entscheidbar** | TM hält immer und gibt korrekte Antwort |
|
||
| **Diagonalisierung** | Beweistechnik: Widerspruch durch Selbstreferenz + Negation |
|
||
| **Zeitkomplexität** | Maximale Schrittzahl einer TM bei Eingabelänge $n$ |
|
||
| **Speicherkomplexität** | Maximale Zahl besuchter Bandzellen bei Eingabelänge $n$ |
|
||
| **Verifier** | Algorithmus der $(w, c)$ prüft – $c$ ist das Zertifikat |
|
||
| **Polynomialzeit-Reduktion** | $A \leq_P B$: Umwandlung von $A$ in $B$ in Polynomialzeit |
|
||
| **NP-vollständig** | In NP + jedes NP-Problem reduzierbar darauf |
|
||
| **NP-hard** | Jedes NP-Problem reduzierbar darauf (muss nicht in NP sein) |
|
||
| **PSPACE-vollständig** | In PSPACE + jedes PSPACE-Problem reduzierbar darauf |
|