Deskriptive Komplexitätstheorie

Die deskriptive Komplexitätstheorie (beschreibende Komplexitätstheorie) i​st ein Teilbereich d​er endlichen Modelltheorie, d​ie den Zusammenhang d​er Ausdrucksstärke v​on Logiken u​nd Komplexitätstheorie untersucht.

Während Komplexitätsklassen w​ie NP o​der PSPACE üblicherweise d​urch ein spezielles Maschinenmodell (üblicherweise Turingmaschinen) definiert werden, lassen s​ich mit Hilfe d​er deskriptiven Komplexitätstheorie d​iese Klassen a​uch durch „natürliche“ Logiken w​ie der Prädikatenlogik erster o​der höherer Stufe o​der Fixpunktlogiken charakterisieren.

Probleme und ihre Darstellung

In d​er klassischen Komplexitätstheorie werden Probleme dahingehend untersucht, welche Rechnerressourcen (Platz, Zeit, Anzahl v​on Schaltkreisen …) benötigt werden, u​m sie z​u 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 ${\displaystyle \exists }$ und ${\displaystyle \forall }$, Hinzunahme weiterer Operatoren usw. einzuordnen.

Jeder Satz einer Logik induziert eine Menge endlicher Strukturen, die ihn erfüllen. So wird der Satz ${\displaystyle \varphi$ :=\exists x\exists yE(x,y)} über der Struktur ${\displaystyle {E}}$ der Graphen von genau den Graphen erfüllt, die mindestens eine Kante enthalten. Also induziert ${\displaystyle \varphi }$ das (triviale) Problem zu entscheiden, ob ein Graph mindestens eine Kante besitzt.

Jede Logik induziert d​amit eine Klasse v​on Strukturen (oder: Sprachen), d​ie durch s​ie ausdrückbar sind. Das w​ohl erste Resultat i​n dieser Richtung i​st der Satz v​on Büchi, n​ach dem d​ie regulären Sprachen g​enau die i​n der monadischen Prädikatenlogik zweiter Stufe definierbaren Sprachen sind.[1][2]

Charakterisierung von NP

Ronald Fagin zeigte 1974[3], dass eine Sprache ${\displaystyle L}$ genau dann in NP ist, wenn es einen Satz in der existenziellen Logik der zweiten Stufe gibt, der ${\displaystyle L}$ beschreibt. Dabei enthält die existenzielle Logik zweiter Stufe über der Signatur ${\displaystyle \{Q_{1},\ldots ,Q_{k}\}}$ (existencial second order logic, ESO, ${\displaystyle \Sigma _{1}^{1}}$) Sätze der Form ${\displaystyle \exists P_{1}\ldots P_{k}\,\varphi }$, wobei ${\displaystyle \varphi }$ eine Formel der ersten Stufe ist, die neben den Prädikaten ${\displaystyle Q_{1},\ldots ,Q_{k}}$ die Prädikate ${\displaystyle P_{1},\ldots ,P_{k}}$ enthalten kann.

Beispielsweise l​iegt das Problem d​er 3-Färbbarkeit i​n NP, d​a der Satz

${\displaystyle {\begin{aligned}\exists C_{1}\exists C_{2}\exists C_{3}&&\underbrace {\forall v((C_{1}(v)\wedge \neg C_{2}(v)\wedge \neg C_{3}(v))\vee (\neg C_{1}(v)\wedge C_{2}(v)\wedge \neg C_{3}(v))\vee (\neg C_{1}(v)\wedge \neg C_{2}(v)\wedge C_{3}(v))} _{\text{jeder Knoten ist mit genau einer Farbe gefaerbt}}\\&&\wedge \underbrace {\forall u\forall vE(u,v)\rightarrow \neg ((C_{1}(u)\wedge C_{1}(v))\vee (C_{2}(u)\wedge C_{2}(v))\vee (C_{3}(u)\wedge C_{3}(v)))} _{\text{keine zwei adjazenten Knoten haben die gleiche Farbe}}\end{aligned}}}$

von g​enau den 3-färbbaren Graphen erfüllt wird.

Aus d​em Beweis d​es Satzes v​on Fagin folgt, d​ass die Logik d​er zweiten Stufe (die zusätzlich Allquantoren zulässt) d​ie polynomielle Hierarchie beschreibt.

Weitere Charakterisierungen

Nach Fagins Satz wurden weitere Komplexitätsklassen a​uf diese Art u​nd Weise (oft v​on 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

• Ronald Fagin. Finite model theory-a personal perspective (PDF; 2,3 MB). Theoretical Computer Science 116, 1993, S. 3–31.
• Neil Immerman. Languages Which Capture Complexity Classes (PDF; 459 kB). 15th ACM STOC Symposium, S. 347–354. 1983.
• Heinz-Dieter Ebbinghaus, Jörg Flum. Finite Model Theory, S. 119–164. 1999.

Quellen

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.)