Inhalt

1. Turingmaschinen, These von Church und Turing

2. Kodierung von Turingmaschinen, die universelle Turingmaschine, das Halteproblem, Unentscheidbarkeit

3. Reduktionen, Post'sche Korrespondenz Problem

Teil II: Komplexitätstheorie

1. Hamiltonsches vs. Eulersches Kreisproblem, Erfüllbarkeitsprobleme DNF-SAT, KNF-SAT

2. Komplexitätsklassen: L, NL, P, NP, PSPACE, EXP, NEXP.

3. Polynomielle Reduktionen, NP-Vollständigkeit, Satz von Cook: SAT ist NP-vollständig.
   Weitere NP-vollständige Problem:
   • 3-SAT
   • HAM
   • TSP
   • Vertex Cover,
   • Clique
   • Subset Sum,
   • Knapsack
   • Partition
   • Bin Packing

4. Approximationsverfahren

5. Vollständige Probleme für NL und PSPACE