Sharp-P

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

Die Klasse wurde 1979 von Leslie Valiant eingeführt.

Definition

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

Beispiel

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

Nach dem Satz von Toda<ref>Seinosuke Toda, PP is as Hard as the Polynomial-Time Hierarchy, SIAM Journal on Computing, Band 20, 1991, S. 865–877</ref> 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:

P ⊆ NP ⊆ PH ⊆ P^#P ⊆ PSPACE

Da #P die Komplexitätsklasse NP enthält sind sie mindestens so schwer zu lösen.<ref>Brian Hayes, Accidental Algorithms, American Scientist, Band 96, Januar/Februar 2008, S. 9–13</ref>

Liste einiger #P-vollständiger Probleme

#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 (also in P ist).

Gibt es ein perfektes Matching in einem allgemeinen Graphen ? Das Problem ist auch in P lösbar.<ref name="cai">Jin-Yi Cai, Computational Complexity and Holographic Algorithms, Vortragsfolien, Abrufbar von Jin-Yi Cai der Webseite von Cai als Talk at MIT and Brown 2008 on Holographic Algorithms</ref>
Permanente (einer 0-1-Matrix)
Anzahl der linearen Erweiterungen einer partiellen Ordnung.

Literatur

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, {{#invoke:Vorlage:Handle|f|scheme=doi|class=plainlinks|parProblem=Problem|errCat=Wikipedia:Vorlagenfehler/Parameter:DOI|errClasses=error editoronly|errHide=1|errNS=0 4 10 100}}

Weblinks

#P. In: Complexity Zoo. (englisch)

Einzelnachweise