Vor Ort
Merkzettel Warenkorb
Produktbild: Vorlesungen zur Komplexitätstheorie
Band 32

Vorlesungen zur Komplexitätstheorie

Aus der Reihe Teubner Texte zur Informatik

59,95 €

inkl. gesetzl. MwSt., Versandkostenfrei

Beschreibung

Produktdetails

Einband

Taschenbuch

Erscheinungsdatum

30.10.2000

Abbildungen

312 S. 1 Abb.

Verlag

Vieweg & Teubner

Seitenzahl

312

Maße (L/B/H)

23,5/16,1/1,8 cm

Gewicht

500 g

Auflage

2000

Sprache

Deutsch

ISBN

978-3-519-00315-1

Beschreibung

Produktdetails

Einband

Taschenbuch

Erscheinungsdatum

30.10.2000

Abbildungen

312 S. 1 Abb.

Verlag

Vieweg & Teubner

Seitenzahl

312

Maße (L/B/H)

23,5/16,1/1,8 cm

Gewicht

500 g

Auflage

2000

Sprache

Deutsch

ISBN

978-3-519-00315-1

Herstelleradresse

Vieweg+Teubner Verlag
Abraham-Lincoln-Straße 46
65189 Wiesbaden
DE

Email: GPSR Kontakt

Ein neues Kapitel für Ihre Bücher

Ein neues Kapitel für Ihre Bücher

Schenken Sie Ihren alten Schätzen ein zweites Leben und erhalten dafür eine Thalia Geschenkkarte.

Jetzt verkaufen
Jetzt verkaufen

Noch keine Bewertungen vorhanden

Verfassen Sie die erste Bewertung zu diesem Artikel

Helfen Sie anderen Kundinnen und Kunden durch Ihre Meinung.

Kundinnen und Kunden meinen

Bewertungen (0)

Weitere Artikel finden Sie in
  • Produktbild: Vorlesungen zur Komplexitätstheorie
  • 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.