15. Jun 2008, 11:45

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.

Inhaltsverzeichnis 1 Definition 2 Beispiel 3 Eigenschaften 4 Liste einiger #P-vollständiger Probleme 5 Literatur 6 Weblinks

[Bearbeiten] Definition

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.

[Bearbeiten] 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?

[Bearbeiten] Eigenschaften

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:

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

[Bearbeiten] 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.

• Permanente (einer 0-1-Matrix)
• Anzahl der linearen Erweiterungen einer partiellen Ordnung [1]

[Bearbeiten] 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, DOI 10.1007/BF00383444, [2]

[Bearbeiten] Weblinks

• #P im Complexity Zoo (englisch)

Dieser Artikel ist eine Kopie aus der freien Enzyklopädie Wikipedia. Am Originalartikel kann jeder Korrekturen und Ergänzungen vornehmen. Zudem kann man frühere Versionen einsehen.

Abkürzungen • Dateiendungen • Netzjargon