Vorlesungen zur Komplexitätstheorie

In diesem Buch werden sowohl elementare Resultate aus der Komplexitätstheorie behandelt als auch Themen wie Polynomialzeithierarchie, probabilistische Klassen oder die Hausdorffsche Hierarchie, Funktionalklassen und Zählklassen. Das Buch ist aus mehrjährigen Vorlesungen des Autors über Komplexitätstheorie entstanden.

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.