Sharp-P
aus Wikipedia, der freien Enzyklopädie
 |
Der korrekte Titel dieses Artikels lautet „#P“. Diese Schreibweise ist aufgrund technischer Einschränkungen derzeit nicht möglich. |
Die Komplexitätsklasse #P (englische Aussprache Sharp-P oder Number-P) ist eine Klasse von so genannte Zählproblemen (im Gegensatz zu den meist betrachteten Komplexitätsklassen, die Entscheidungsprobleme behandeln). #P-Probleme sind eng verwandt mit den zugehörigen NP-Problemen.
Die Klasse wurde 1979 von Leslie Valiant eingeführt.
Inhaltsverzeichnis |
[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.
Nach dem Satz von Toda reicht eine P-Maschine mit #P-Orakel (P#P), um alle Sprachen in PH mit nur einer Orakelfrage zu entscheiden. Dies ist ein Hinweis für die enorme Schwierigkeit, #P-Probleme exakt zu lösen.
[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] Liste einiger #P-vollständiger Probleme
- #SAT
- Anzahl Matchings eines bipartiten Graphen
- 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)
