Dr. R. Winter


Vorlesung

Komplexitätstheorie

Hauptstudium Informatik

Übersicht siehe unter Komplexitätstheorie 




1.	Grundlagen


1.1.	Mathematische Grundlagen
1.2.	Verallgemeinerte Turingmaschinen mit Speichermedium Graph, Typen von Turingmaschinen
1.3.	Elementare Techniken beim Rechnen mit Turingmaschinen



2.	Komplexität von Turingmaschinen


2.1.	Komplexitätsmaß
2.2.	Komplexitätsklassen
2.3.	Diagonalisierung
2.4.	Bandreduktion und Kompression
2.5.	Beschleunigung
2.6.	Simulationskomplexität bei universellen Turingmaschinen
2.7.	Konstruierbarkeit



3.      Registermaschinen 

3.1.    Das RAM-Modell
3.2.    Zusammenhänge zwischen RAM, PASCALLI, PASCALLINO und Turingmaschinen
        Zeitkomplexitätsabschätzung 



4.	Nachweis von unteren Schranken


4.1.	Die Crossing-Sequenz-Methode und ihre Anwendung. Satz von Barsdin
4.2.	Rckkehrmaß zur Charakterisierung von Sprachklassen



5.      Obere Schranken für Sprachklassen


5.1.	Zeitkomplexitätsaussagen
5.2.	Bandkomplexitätsaussagen



6.	Sequentielle Komplexitätsklassen


6.1.    Definitionen sequentieller Komplexitätsklassen
6.2.    Der satz von Savitch
6.3.    Hierarchiesätze zu sequentiellen Komplexitätsklassen
6.4.    NP-Vollständigkeit
6.5.    PseudopolynomielleAlgorithmen und starke NP-Vollständigkeit
6.6.    NP-harte, NP-leichte und NP-äquivalente Probleme
6.7.    Approximationsalgorithmen
6.8.    Probabilistische Algorithmen
6.9.    Verschiedene Reduzierbarkeitsbegriffe. Unentscheidbarkeitsgrad
6.10.   Vollständigkeit allgemein
6.11.   Das LBA-Problem
6.12.   PSPACE-Vollständigkeit

Literatur

R. Winter