Berechenbarkeit und Komplexität

Sebastian Gottwald, Ulm University

Der Gödelsche Satz und PCP (Notizen)

Einführung
- Überblick: Semi-entscheidbare Probleme
- Vorschau: Anstehende reduktionen und Komplexitätstheorie
- Vorschau: Der Gödelsche Unvollständigkeitssatz
Postsches Korrespondenzproblem (PCP)
- Beispiele
- Definition: PCP
- Bemerkung: PCP ist semi-entscheidbar aber nicht entscheidbar
- Definition: MPCP
- Lemma: MPCP reduzierbar auf PCP
- Lemma: H reduzierbar auf MPCP
- Satz: MPCP und PCP nicht-entscheidbar (=> H semi-entscheidbar)
Zwei wichtige Reduktionen
- PCP reduzierbar auf WA (=> WA nicht entscheidbar, Gödel)
- PCP reduzierbar auf PL (gültige prädikatenlogische Formeln)

Einführung
- Bemerkung: Complexity zoo
- O-Notation
- Beispiele
P
- Definition: Zeitfunktionen deterministischer Turing-Maschinen (TMs)
- Definition: P (Entscheidungsprobleme polynomieller Laufzeit)
- Bemerkung/Beispiele: Kostenmaße
- Bemerkung: Komplexität häufiger Operationen
NP
- Definition: Nicht-deterministische Turing-Maschinen (NTM)
- Vergleich von akzeptierten Sprachen: deterministisch vs. nicht-deterministisch
- Satz: NTMs erschließen keine neue Klasse von (semi-)entscheidbaren Problemen.
- Definition: Zeitfunktionen nicht-deterministischer Turing-Maschinen
- Definition: NP
- Beispiel: SAT
- Bemerkung: NP liegt in der Menge der berechenbaren Sprachen
- Bemerkung: Punktweise Zeitfunktion für NTMs
- Bemerkung: Guess and Check-Argument

Polynomielle Reduzierbarkeit
- Definition: Polynomielle Reduzierbarkeit
- Technisches Lemma: Zeitkomplexität von Hintereinanderschaltungen
- Korollar: Transitivität der polynomiellen Reduktion, sowie Zugehörigkeit zu P/NP von reduzierten Sprachen
NP-Vollständigkeit
- Definition: NP-Härte und -Vollständigkeit
- Satz: Die Existenz von deterministischen polynomiellen Algorithmen für NP-vollständige Probleme würde P=NP beweisen
NP-vollständige Probleme
- SAT
- 3-SAT
- SUBSETSUM
- PARTITION
- BIN PACKING
- EULER-KREIS
- HAMILTON-KREIS
- TRAVELING SALESPERSON (Simulation,Komplexität)