Overview

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.

Full Product Details

Author:   Gerd Wechsung
Publisher:   Springer Fachmedien Wiesbaden
Imprint:   Vieweg+Teubner Verlag
Edition:   2000 ed.
Volume:   32
Dimensions:   Width: 16.10cm , Height: 1.70cm , Length: 23.50cm
Weight:   0.500kg
ISBN:  

9783519003151

ISBN 10:   3519003155
Pages:   312
Publication Date:   30 October 2000
Audience:   Professional and scholarly ,  Professional & Vocational
Format:   Paperback
Publisher's Status:   Active
Availability:   In Print  
This item will be ordered in for you from one of our suppliers. Upon receipt, we will promptly dispatch it out to you. For in store availability, please contact us.
Language:   German

Table of Contents

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.

Reviews

Author Information

Prof. Dr. Gerd Wechsung, Universität Jena

Tab Content 6

Author Website:  

Countries Available

All regions