Vorlesung

Sequentielle und parallele Komplexitätstheorie

Hauptstudium Informatik

Inhalt der Vorlesung:

Aufbauend auf den Grundbegriffen zur Komplexitätstheorie in der Vorlesung Informatik IV (Theoretische Informatik I) im Grundstudium beschäaftigen wir uns in dieser Vorlesung zur Komplexitätstheorie mit folgenden Schwerpunkten:

Allgemeine Komplexitätsmaße für Turing- und Registermaschinen
Zeit- und Speicherplatzgewinn
Zeitkomplexitätsschranken, CROSSING-Sequence
Deterministische und nichtdeterministische Hierarchiesätze, Gap-Theoreme
Sequentielle Komplexitätsklassen, NP- und PSPACE-Vollständigkeit
Parallele Komplexitätsklassen basierend auf dem ATM-Modell, NC- und AC-Klassen
Hierarchien von Komplexitätsklassen, Polynomiale Zeithierarchie
Komplexität von Spielen
Komplexitätsgewinn durch Verwendung von parallelen Registermaschinen

Literatur:

Reischuk. Eine Einführung in die Komplexitätstheorie. Teubner Stuttgart 1990
Papadimitriou. Computational Complexity. Addison-Wesley 1994
Hopcroft, Ullman. Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison-Wesley 1993
Wagner, Wechsung. Computational Complexity. Mathematische Monographien Bd.19. Berlin 1986

Bemerkungen:

Voraussetzung: Besuch der Lehrveranstaltung Informatik IV
Ein Übungsschein kann durch aktive Mitarbeit in den Übungen und korrekte Bearbeitung der gestellten Übungsaufgaben erworben werden.
Der Vorlesungsstoff wird im Rahmen der Diplomprüfung Theoretische Informatik geprüft oder kann als Bestandteil der Vertiefungsrichtung Theoretische Informatik verwendet werden. Verbindung zu einer Projektarbeit ist möglich.



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.	Nachweis von unteren Schranken

3.1.	Die crossing-Sequenz-Methode und ihre Anwendung
3.2.	Rckkehrmaß: zur Charakterisierung von Sprachklassen


4.      Hierarchiebetrachtungen bei Zeit- und Platzkomplexität

4.1.	Gap-Theoreme fr Zeit- und Bandkomplexität
4.2.    Allgemeiner Hierarchiesatz. Zeit- und Platzhierarchiesätze


5.      Wichtige sequentielle Komplexitätsklassen
5.1.    Definitionen
5.2.	Der Satz von Savitch
5.3.    Nichtdeterministische und deterministische Zeitklassen
5.4.    Hierarchiebetrachtung bei sequentiellen Komplexitätsklassen


6.      NP-Vollständigkeit
6.1.    Definitionen und Sätze
6.2.    NP-Vollständigkeit von SAT und 3SAT
6.3.    NP-Vollständigkeit von KP
6.4.    Die Klassen NP, co-NP und das Primzahlproblem
6.5.    Vollständigkeit allgemein
 

7.	Die LBA-Probleme

7.1.	Vollstätndigkeit in PSPACE
7.2.	Das erste LBA-Problem
7.3.	Das zweite LBA-Problem - Satz von Immerman / Szelepcsenyi


8.	Parallele Komplexitätsklassen

8.1.	RAM und PRAM
8.2.	Parallele Berechnungen in polylogarithmischer Zeit.Die Klasse NC
8.3.    Zusammenhang zwischen P und NC
8.4.    Die Klassen AC und SC
8.5.    Hierarchieuntersuchungen bei NC, AC und SC

Literatur

Reischuk: Einfhrung in die Komplexitätstheorie Teubner 1990
Balcazar/Diaz/Gabarro:Structural Complexity II Springer Berlin - Heidelberg 1990
Papadimitriou: Computational Complexity Addison - Wesley 1994

R. Winter