Sharp-P

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Icon falscher Titel.svg Der korrekte Titel dieses Artikels lautet „#P“. Diese Schreibweise ist aufgrund technischer Einschränkungen nicht möglich.

Die Komplexitätsklasse #P (englische Aussprache Sharp-P oder Number-P) ist eine Klasse von so genannten Zählproblemen (im Gegensatz zu den meist betrachteten Komplexitätsklassen, die Entscheidungsprobleme behandeln). Viele #P-Probleme sind eng verwandt mit den zugehörigen NP-Problemen.

Die Klasse wurde 1979 von Leslie Valiant eingeführt.

Definition[Bearbeiten]

Ein Problem ist in der Klasse #P, wenn eine nichtdeterministische Turingmaschine existiert, die polynomiell zeitbeschränkt ist und für jede Instanz I des Problems genau so viele akzeptierende Berechnungspfade hat, wie es Lösungen zu der Instanz I gibt.

Beispiel[Bearbeiten]

Ein bekanntes Entscheidungsproblem aus NP ist das Erfüllbarkeitsproblem der Aussagenlogik (SAT):

  • Existiert zu einer gegebenen aussagenlogischen Formel eine erfüllende Variablenbelegung?

Das zugehörige Zählproblem aus #P wird mit #SAT bezeichnet und lautet:

  • Wie viele erfüllende Variablenbelegungen gibt es zu einer gegebenen aussagenlogischen Formel?

Eigenschaften[Bearbeiten]

Nach dem Satz von Toda reichen deterministische polynomiell zeitbeschränkte Turingmaschinen, die eine einzige Orakel-Anfrage an ein Problem aus #P stellen dürfen, um die Sprachen in PH zu entscheiden. Dies ist ein Hinweis für die enorme Schwierigkeit, #P-Probleme exakt zu lösen. Andererseits kann in polynomiellem Platz der Berechnungsbaum einer nichtdeterministischen, polynomiell zeitbeschränkten Turingmaschine vollständig durchsucht werden, so dass sich alle #P-Probleme in polynomiellen Platz berechnen lassen. Damit lässt sich #P wie folgt in Beziehung zu anderen wichtigen Komplexitätsklassen setzen:

PNPPH ⊆ P#PPSPACE

Liste einiger #P-vollständiger Probleme[Bearbeiten]

  • #SAT
  • Anzahl der perfekten Matchings eines bipartiten Graphen
Diese Tatsache ist besonders interessant, weil das zugehörige Entscheidungsproblem (Existenz von perfekten Matchings in bipartiten Graphen) deterministisch in polynomieller Zeit lösbar ist.
  • Permanente (einer 0-1-Matrix)
  • Anzahl der linearen Erweiterungen einer partiellen Ordnung [1]

Literatur[Bearbeiten]

  • Leslie G. Valiant: The complexity of computing the permanent. Theoretical Computer Science, 8:189-201, 1979
  • Graham Brightwell, Peter Winkler: Counting linear extensions, Order, Volume 8, Issue 3, Sep 1991, Pages 225 - 242, DOI 10.1007/BF00383444, [2]

Weblinks[Bearbeiten]

  • #P. In: Complexity Zoo. (englisch)