Vorlesungen zur Komplexitätstheorie

Prof. Dr. Gerd Wechsung, Universität Jena

Symbolverzeichnis.- 1 Hierarchien von Komplexitätsklassen.- 1.1 Komplexitätsmaße und -klassen.- 1.2 Existenz beliebig schwieriger Probleme.- 1.3 Kompression und Beschleunigung.- 1.4 Hierarchiesätze.- 1.5 Untere Schranken.- 2 Zwischen L und PSPACE.- 2.1 Einfache Inklusionsbeziehungen.- 2.2 Komplexitätsbeschränkte m-Reduktionen.- 2.3 Vollständige Probleme in NL.- 2.4 Vollständige Probleme in P.- 2.5 Das P-NP-Problem.- 3 Die Polynomialzeithierarchie.- 3.1 Weitere Reduktionsbegriffe.- 3.2 Die Polynomialzeithierarchie.- 3.3 Akzeptierungstypen für $$\Delta _2^P $$ und $$\Theta _2^P $$.- 3.4 Alternierende Maschinen.- 3.5 Alternierende Komplexitätsklassen.- 3.6 Weitere Vollständigkeitsresultate.- 3.7 Blattsprachenklassen.- 3.8 Relativierungen.- 4 Einige besondere Resultate.- 4.1 Der Satz von Savitch.- 4.2 coNSPACE-Klassen.- 4.3 Blockrespektierende Berechnungen.- 4.4 Raum ist besser als Zeit.- 4.5 DLINTIME ? NUNTIME.- 5 Dünne vollständige bzw. harte Mengen.- 5.1 Dünne Mengen.- 5.2 Nichtuniforme Berechnungen.- 5.3 Das Isomorphieproblem.- 5.4 Dünne btt-harte Mengen für NP.- 5.5 Dünne T-harte Mengen für NP.- 6 Die Hausdorffsche Hierarchie über NP.- 6.1 Der Boolesche Abschluß von NP.- 6.2 Akzeptierungstypen für die BHk(NP).- 6.3 Erweiterung der Hausdorffschen Hierarchie.- 6.4 tt-Charakterisierung der BHk(NP).- 6.5 Die Fragehierarchie.- 6.6 Vollständige Probleme.- 6.7 Kann die Hausdorffsche Hierarchie endlich sein?.- 6.8 Verschiedene Orakel.- 7 Zählklassen.- 7.1 Zählklassen von endlichem Typ.- 7.2 Die einfachste Zählklasse.- 7.3 Die Klasse ?P.- 7.4 Längenabhängige Akzeptierungstypen.- 7.5 Promise-Klassen.- 8 Probabilistische Klassen.- 8.1 Die Klassen RP und ZPP.- 8.2 Die Klassen PP und G=P.- 8.3 Beschränkte Fehlerwahrscheinlichkeit.- 8.4 DerMehrheitsquantor.- 8.5 Die Arthur-Merlin-Hierarchie.- 8.6 Operatoren.- 8.7 Die Ergebnisse von Toda.- 9 Funktionenklassen.- 9.1 Funktionen- und Relationenanaloga zu P und NP.- 9.2 Verfeinerungen von Relationen.- 9.3 Anzahl von Lö.- 9.4 Konstruktion von Lösungen.- 9.5 Selbstreduzierbarkeit.- 9.6 Optimale Lösungen.- 10 Lowness und Highness.- 10.1 Die low- und die high-Hierarchie.- 10.2 Einordnung konkreter Klassen.- 10.3 Selektivität.- 10.4 Graphisomorphie.- A Mathematische Grundlagen.- A.1 Logische Grundbegriffe.- A.2 Mengen, Relationen, Funktionen.- A.2.1 Mengen.- A.2.2 Relationen.- A.2.3 Funktionen.- A.2.4 Asymptotisches Wachstum.- A.3 Formale Sprachen.- A.4 Turingmaschinen und Berechenbarkeit.- Autorenverzeichnis.- Sachwortverzeichnis.