UID:
almahu_9948191429802882
Umfang:
312 S. 1 Abb.
,
online resource.
Ausgabe:
1st ed. 2000.
ISBN:
9783322800244
Serie:
Teubner Texte zur Informatik, 32
Anmerkung:
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 Der Mehrheitsquantor -- 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.
In:
Springer eBooks
Weitere Ausg.:
Printed edition: ISBN 9783519003151
Sprache:
Deutsch
DOI:
10.1007/978-3-322-80024-4
URL:
https://doi.org/10.1007/978-3-322-80024-4
