Deskriptive Komplexitätstheorie

2022-12-26T18:50:57Z

77.117.161.167: /* Charakterisierung von NP */Tippfehler

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ätsklasse]]n wie [[NP (Komplexitätsklasse)|NP]] oder [[PSPACE]] üblicherweise durch ein spezielles Maschinenmodell (üblicherweise [[Turingmaschine]]n) 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 ==

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 <math>\exists</math> und <math>\forall</math>, Hinzunahme weiterer Operatoren usw. einzuordnen.

Jeder Satz einer Logik induziert eine Menge endlicher [[Struktur (erste Stufe)|Strukturen]], die ihn erfüllen. So wird der Satz <math>\varphi:=\exists x\exists y E(x,y)</math> über der Struktur <math>{E}</math> der Graphen von genau den Graphen erfüllt, die mindestens eine Kante enthalten. Also induziert <math>\varphi</math> 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äre Sprache|regulären Sprachen]] genau die in der [[Monadische Prädikatenlogik zweiter Stufe|monadischen Prädikatenlogik zweiter Stufe]] definierbaren Sprachen sind.<ref>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</ref><ref>Leonid Libkin: ''Elements of Finite Model Theory'', Springer-Verlag (2004), ISBN 3-540-21202-7, Satz 7.21</ref>

== Charakterisierung von NP ==

[[Ronald Fagin]] [[Satz von Fagin|zeigte]] 1974<ref> Ronald Fagin, Generalized first-order spectra and polynomial-time recognizable
sets, in: Complexity of Computation von [[Richard M. Karp]] (Hrsg.)</ref>, dass eine Sprache <math>L</math> genau dann in NP ist, wenn es einen Satz in der ''existenziellen Logik der zweiten Stufe'' gibt, der <math>L</math> beschreibt. Dabei enthält die existenzielle Logik zweiter Stufe über der Signatur <math>\{Q_1,\ldots,Q_k\}</math> (''existential second order logic'', ESO, <math>\Sigma_1^1</math>) Sätze der Form <math>\exists P_1 \ldots P_k\,\varphi</math>, wobei <math>\varphi</math> eine Formel der ersten Stufe ist, die neben den Prädikaten <math>Q_1,\ldots,Q_k</math> die Prädikate <math>P_1,\ldots,P_k</math> enthalten kann.

Beispielsweise liegt das Problem der [[Dreifarbenproblem|3-Färbbarkeit]] in NP, da der Satz

<math>\begin{align}\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 v E(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{align}</math>

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

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

== Weitere Charakterisierungen ==

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 [[Fixpunktlogik]]en beschreiben [[P (Komplexitätsklasse)|P]] beziehungsweise PSPACE auf geordneten Strukturen

== Literatur ==

* Ronald Fagin. [http://www.almaden.ibm.com/cs/people/fagin/tcs93.pdf Finite model theory-a personal perspective] (PDF; 2,3 MB). Theoretical Computer Science 116, 1993, S. 3–31.
* Neil Immerman. [http://www.cs.umass.edu/~immerman/pub/capture.pdf 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 ==

<references/>

{{DEFAULTSORT:Komplexitatstheorie, Deskriptive}}
[[Kategorie:Mathematische Logik]]
[[Kategorie:Komplexitätstheorie]]

Wikipedia (Deutsch) – Lokale Kopie - Benutzerbeiträge [de]

Deskriptive Komplexitätstheorie