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
[Bearbeiten | Quelltext bearbeiten]Ein Problem ist in der Klasse #P, wenn eine nichtdeterministische Turingmaschine existiert, die polynomiell zeitbeschränkt ist und für jede Instanz des Problems genau so viele akzeptierende Berechnungspfade hat, wie es Lösungen zu der Instanz gibt.
Beispiel
[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]Nach dem Satz von Toda[1] 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:
Da #P die Komplexitätsklasse NP enthält sind sie mindestens so schwer zu lösen.[2]
Liste einiger #P-vollständiger Probleme
[Bearbeiten | Quelltext 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 (also in P ist).
- Gibt es ein perfektes Matching in einem allgemeinen Graphen ? Das Problem ist auch in P lösbar.[3]
- Permanente (einer 0-1-Matrix)
- Anzahl der linearen Erweiterungen einer partiellen Ordnung.
Literatur
[Bearbeiten | Quelltext 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
Weblinks
[Bearbeiten | Quelltext bearbeiten]- #P. In: Complexity Zoo. (englisch)
Einzelnachweise
[Bearbeiten | Quelltext bearbeiten]- ↑ Seinosuke Toda, PP is as Hard as the Polynomial-Time Hierarchy, SIAM Journal on Computing, Band 20, 1991, S. 865–877
- ↑ Brian Hayes, Accidental Algorithms, American Scientist, Band 96, Januar/Februar 2008, S. 9–13
- ↑ 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