Beschreibende Komplexität -Descriptive Complexity
Descriptive Complexity ist ein Buch in mathematischer Logik und rechnerischer Komplexitätstheorie von Neil Immerman . Es handelt sich um eine deskriptive Komplexitätstheorie , ein Bereich, in dem gezeigt wird, dass die Ausdruckbarkeit mathematischer Eigenschaften unter Verwendung verschiedener Arten von Logik ihrer Berechenbarkeit in verschiedenen Arten von ressourcengebundenen Berechnungsmodellen entspricht. Es wurde 1999 vom Springer-Verlag in seiner Buchreihe Graduate Texts in Computer Science veröffentlicht.
Themen
Das Buch enthält 15 Kapitel, die grob in fünf Kapitel zur Logik erster Ordnung , drei zur Logik zweiter Ordnung und sieben unabhängige Kapitel zu fortgeschrittenen Themen unterteilt sind.
Die ersten beiden Kapitel enthalten Hintergrundmaterial zur Logik erster Ordnung (einschließlich Arithmetik erster Ordnung , dem BIT-Prädikat und dem Begriff einer Abfrage erster Ordnung) und zur Komplexitätstheorie (einschließlich formaler Sprachen , ressourcengebundener Komplexitätsklassen und vollständiger Probleme) ). Kapitel drei beginnt die Verbindung zwischen Logik und Komplexität mit einem Beweis, dass die erkennbaren Sprachen erster Ordnung im logarithmischen Raum erkannt werden können , und der Konstruktion vollständiger Sprachen für den logarithmischen Raum, den nichtdeterministischen logarithmischen Raum und die Polynomzeit . Das vierte Kapitel befasst sich mit induktiven Definitionen, Festpunktoperatoren und der Charakterisierung der Polynomzeit im Sinne einer Logik erster Ordnung mit dem Operator mit dem geringsten Festpunkt. Der Teil des Buches zu Themen erster Ordnung endet mit einem Kapitel über logische Charakterisierungen von Ressourcengrenzen für Maschinen mit parallelem Direktzugriff und die Komplexität von Schaltkreisen .
In Kapitel 6 werden Ehrenfeucht-Fraïssé-Spiele vorgestellt , ein Schlüsselwerkzeug zum Nachweis der logischen Unaussprechlichkeit, und in Kapitel 7 wird die Logik zweiter Ordnung vorgestellt. Es enthält Fagins Theorem, das die nichtdeterministische Polynomzeit im Sinne einer existenziellen Logik zweiter Ordnung charakterisiert , das Cook-Levin-Theorem über die Existenz von NP-vollständigen Problemen und die Erweiterung dieser Ergebnisse auf die Polynomhierarchie . Kapitel 8 verwendet Spiele, um die Unaussprechlichkeit bestimmter Sprachen in der Logik zweiter Ordnung zu beweisen.
Kapitel neun befasst sich mit der Komplementation von Sprachen und dem Operator der transitiven Schließung , einschließlich des Immerman-Szelepcsényi-Theorems, dass der nichtdeterministische logarithmische Raum unter Komplementation geschlossen wird. Kapitel 10 enthält vollständige Probleme und eine logische Charakterisierung des Polynomraums zweiter Ordnung . Kapitel 11 befasst sich mit der Einheitlichkeit der Schaltungskomplexität (der Unterscheidung zwischen der Existenz von Schaltungen zur Lösung eines Problems und ihrer algorithmischen Konstruierbarkeit), und Kapitel 12 befasst sich mit der Rolle des Ordnens und Zählens von Prädikaten bei logischen Charakterisierungen von Komplexitätsklassen. Kapitel 13 verwendet das Switching-Lemma für Untergrenzen, und Kapitel 14 befasst sich mit Anwendungen auf Datenbanken und Modellprüfungen . Ein letztes Kapitel beschreibt Themen, die in diesem Bereich noch erforschungsbedürftig sind.
Publikum und Empfang
Das Buch richtet sich in erster Linie an Forscher in diesem Bereich, kann aber auch als Grundlage für einen Graduiertenkurs verwendet werden und ist mit Übungen für diesen Zweck ausgestattet. Obwohl es behauptet, in sich geschlossen zu sein, schreibt der Rezensent W. Klonowski, dass seine Leser sowohl die klassische Komplexität als auch die Grundlagen der mathematischen Logik bereits verstehen müssen.
Der Rezensent Anuj Dawar schreibt, dass ein Teil des frühen Versprechens der deskriptiven Komplexität durch seine Unfähigkeit, logische Werkzeuge auf die Kernprobleme der Komplexitätstheorie anzuwenden, und durch die Notwendigkeit, rechnerische Ergänzungen zu logischen Sprachen hinzuzufügen, um sie zu verwenden, gedämpft wurde sie, um die Berechnung zu charakterisieren. Dennoch, schreibt er, ist das Buch nützlich, um Forscher in diese Forschungsrichtung einzuführen und um die Komplexität der Berechnungen weniger genau zu untersuchen.