Die deskriptive Komplexitätstheorie (beschreibende Komplexitätstheorie) ist ein Teilbereich der endlichen Modelltheorie, die den Zusammenhang der Ausdrucksstärke von Logiken und Komplexitätstheorie untersucht.

Während Komplexitätsklassen wie NP oder PSPACE üblicherweise durch ein spezielles Maschinenmodell (üblicherweise Turingmaschinen) definiert werden, lassen sich mit Hilfe der deskriptiven Komplexitätstheorie diese Klassen auch durch „natürliche“ Logiken wie der Prädikatenlogik erster oder höherer Stufe oder Fixpunktlogiken charakterisieren.

Probleme und ihre Darstellung

Bearbeiten

In der klassischen Komplexitätstheorie werden Probleme dahingehend untersucht, welche Rechnerressourcen (Platz, Zeit, Anzahl von Schaltkreisen …) benötigt werden, um sie zu lösen.

Der Ansatz der deskriptiven Komplexitätstheorie ist es dagegen, Probleme in Hinblick auf die logischen Ressourcen, wie die Anzahl von Quantoren, Anzahl Alternationen von   und  , Hinzunahme weiterer Operatoren usw. einzuordnen.

Jeder Satz einer Logik induziert eine Menge endlicher Strukturen, die ihn erfüllen. So wird der Satz   über der Struktur   der Graphen von genau den Graphen erfüllt, die mindestens eine Kante enthalten. Also induziert   das (triviale) Problem zu entscheiden, ob ein Graph mindestens eine Kante besitzt.

Jede Logik induziert damit eine Klasse von Strukturen (oder: Sprachen), die durch sie ausdrückbar sind. Das wohl erste Resultat in dieser Richtung ist der Satz von Büchi, nach dem die regulären Sprachen genau die in der monadischen Prädikatenlogik zweiter Stufe definierbaren Sprachen sind.[1][2]

Charakterisierung von NP

Bearbeiten

Ronald Fagin zeigte 1974[3], dass eine Sprache   genau dann in NP ist, wenn es einen Satz in der existenziellen Logik der zweiten Stufe gibt, der   beschreibt. Dabei enthält die existenzielle Logik zweiter Stufe über der Signatur   (existential second order logic, ESO,  ) Sätze der Form  , wobei   eine Formel der ersten Stufe ist, die neben den Prädikaten   die Prädikate   enthalten kann.

Beispielsweise liegt das Problem der 3-Färbbarkeit in NP, da der Satz

 

von genau den 3-färbbaren Graphen erfüllt wird.

Aus dem Beweis des Satzes von Fagin folgt, dass die Logik der zweiten Stufe (die zusätzlich Allquantoren zulässt) die polynomielle Hierarchie beschreibt.

Weitere Charakterisierungen

Bearbeiten

Nach Fagins Satz wurden weitere Komplexitätsklassen auf diese Art und Weise (oft von Neil Immerman) charakterisiert:

  • Die Prädikatenlogik der ersten Stufe mit einem Operator zur Bildung der transitiven Hülle beschreibt NLOGSPACE
  • Die Prädikatenlogik der ersten Stufe mit einem deterministischen Operator zur Bildung der transitiven Hülle beschreibt LOGSPACE
  • Die Logik der zweiten Stufe mit einem transitiven Hüllenoperator beschreibt PSPACE
  • verschiedene Fixpunktlogiken beschreiben P beziehungsweise PSPACE auf geordneten Strukturen

Literatur

Bearbeiten
  1. J. R. Büchi: Weak second-order arithmetic and finite automata, Zeitschrift für mathematische Logik und Grundlagen der Mathematik (1960), Band 6, Seiten 66–92
  2. Leonid Libkin: Elements of Finite Model Theory, Springer-Verlag (2004), ISBN 3-540-21202-7, Satz 7.21
  3. Ronald Fagin, Generalized first-order spectra and polynomial-time recognizable sets, in: Complexity of Computation von Richard M. Karp (Hrsg.)