Church-Turing-These, DTMs, NTMs, Mehrband-Maschinen

P, NP, ExpTime, Polyzeit-Reduktionen

Satz von Cook/Levin, 3SAT, Vertex Cover, Clique, 3-Färbbarkeit, stark NP-vollständig, NP-Zertifikate

coNP-Vollständigkeit

PSpace, Satz von Savitch

QBF, Geography

Syntax und Sematik, Normalformen, Erfüllbarkeit und Gültigkeit, funktionale Vollständigkeit

Motivation, Syntax und Semantik, Auswertung, Erfüllbarkeit, Ehrenfeucht-Fraïssé-Spiele, Sätze von Löwenheim-Skolem, Kompaktheitssatz

NTMs und Typ-0-Sprachen, LBAs und Typ1-Sprachen

SAT, 3SAT, Resolution, 2SAT, Horn-SAT, Markierungsalgorithmus

Alternierende endliche Automaten

Safra-Konstruktion

NP-Vollständigkeit, Satz von Ladner, Satz von Mahaney, Constrains Satisfaction Probleme, Platzkomplexität, Schaltkreiskomplexität, Polyzeit-Hierarchie, Alternierende Turingmaschinen, Satz von Baker, Gill, Solovay