Sharp-P

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 I des Problems genau so viele akzeptierende Berechnungspfade hat, wie es Lösungen zu der Instanz I gibt.

Beispiel

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

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

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

Da #P die Komplexitätsklasse NP enthält sind sie mindestens so schwer zu lösen.

Liste einiger #P-vollständiger Probleme

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).