Del 32 i serien Teubner Texte zur Informatik

Vorlesungen zur Komplexitätstheorie

Häftad, Tyska, 2000

799 kr

Beställningsvara. Skickas inom 10-15 vardagar. Fri frakt för medlemmar vid köp för minst 249 kr.

Elementare Resultate aus der Komplexitatstheorie werden in diesem Buch ebenso behandelt wie auch die Themen Polynomialzeithierarchie, probabilistische Klassen oder die Hausdorffsche Hierarchie, Funktionalklassen und Zahlklassen. Das Buch ist aus mehrjahrigen Vorlesungen des Autors uber Komplexitatstheorie entstanden.

Produktinformation

Utgivningsdatum2000-10-30
Mått161 x 235 x 18 mm
Vikt500 g
FormatHäftad
SpråkTyska
SerieTeubner Texte zur Informatik
Antal sidor312
Upplaga2000
FörlagSpringer Fachmedien Wiesbaden
ISBN9783519003151

Tillhör följande kategorier

Systemvetenskap och AI inom Data och IT
Programmeringsböcker inom Data och IT

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.