Deskriptive Komplexität

Deskriptive Komplexität

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.

Inhaltsverzeichnis

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

Jeder Satz einer Logik induziert eine Menge endlicher Strukturen, die ihn erfüllen. So wird der Satz \varphi:=\exists x\exists y E(x,y) über der Struktur E der Graphen von genau den Graphen erfüllt, die mindestens eine Kante enthalten. Also induziert \varphi 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.

Charakterisierung von NP

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

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

\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}

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

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 PTIME beziehungsweise PSPACE

Literatur

Quellen

  1. Ronald Fagin, Generalized first-order spectra and polynomial-time recognizable sets, in: Complexity of Computation von Richard M. Karp (Hrsg.)

Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Universelle Wahrscheinlichkeitsschranke — Eine Universelle Wahrscheinlichkeitsschranke ist ein angenommener Wert, unterhalb dessen die Wahrscheinlichkeit eines zufälligen Ereignisses so gering ist, dass man es als praktisch unmöglich einordnen kann. Er wird in der Wissenschaft nicht… …   Deutsch Wikipedia

  • Data Mining — Unter Data Mining (englisch für „Datenschürfen“) versteht man die systematische Anwendung von Methoden, die meist statistisch mathematisch begründet sind, auf einen Datenbestand mit dem Ziel der Mustererkennung. Hierbei geht es vor allem um das… …   Deutsch Wikipedia

  • Data mining — Unter Data Mining (englisch für „Datenschürfen“) versteht man die systematische Anwendung von Methoden, die meist statistisch mathematisch begründet sind, auf einen Datenbestand mit dem Ziel der Mustererkennung. Hierbei geht es vor allem um das… …   Deutsch Wikipedia

  • Dataminer — Unter Data Mining (englisch für „Datenschürfen“) versteht man die systematische Anwendung von Methoden, die meist statistisch mathematisch begründet sind, auf einen Datenbestand mit dem Ziel der Mustererkennung. Hierbei geht es vor allem um das… …   Deutsch Wikipedia

  • Datamining — Unter Data Mining (englisch für „Datenschürfen“) versteht man die systematische Anwendung von Methoden, die meist statistisch mathematisch begründet sind, auf einen Datenbestand mit dem Ziel der Mustererkennung. Hierbei geht es vor allem um das… …   Deutsch Wikipedia

  • Datenschürfung — Unter Data Mining (englisch für „Datenschürfen“) versteht man die systematische Anwendung von Methoden, die meist statistisch mathematisch begründet sind, auf einen Datenbestand mit dem Ziel der Mustererkennung. Hierbei geht es vor allem um das… …   Deutsch Wikipedia

  • Matchplus — Unter Data Mining (englisch für „Datenschürfen“) versteht man die systematische Anwendung von Methoden, die meist statistisch mathematisch begründet sind, auf einen Datenbestand mit dem Ziel der Mustererkennung. Hierbei geht es vor allem um das… …   Deutsch Wikipedia

  • Prozess und Realität — Der Essay Prozess und Realität ist ein zuerst 1929 in New York unter dem Originaltitel Process and Reality: An Essay in Cosmology erschienenes Werk des britischen Philosophen und Mathematikers Alfred North Whitehead (1861–1947). Es ist… …   Deutsch Wikipedia

  • Kreditwürdigkeitsprüfung — Die Kreditwürdigkeitsprüfung ist bei Kreditinstituten die erstmalige und laufende Überwachung der Zahlungsfähigkeit und Zahlungswilligkeit ( Bonität ) eines Schuldners. Dieser Vorgang ist bei Kreditvergaben von Banken allgemein verbindlich in… …   Deutsch Wikipedia

  • Arzneimittelepidemiologie — Das Arbeitsgebiet der Pharmakoepidemiologie kann als Grundlagenwissenschaft der Arzneimittelsicherheit verstanden werden. Die Pharmakoepidemiologie wird in einschlägigen Nachschlagewerken als Lehre von dem, was mit/in der Bevölkerung durch die… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”