https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=Sharp-PSharp-P - Versionsgeschichte2026-05-23T14:08:49ZVersionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale KopieMediaWiki 1.43.8https://wiki-de.moshellshocker.dns64.de/index.php?title=Sharp-P&diff=275520&oldid=previmported>Girus: typo , lf2022-06-20T04:38:46Z<p>typo , lf</p>
<p><b>Neue Seite</b></p><div>{{Korrekter Titel|#P}}<br />
Die [[Komplexitätsklasse]] '''#P''' ([[Englische Sprache|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 (Komplexitätsklasse)|NP]]-Problemen.<br />
<br />
Die Klasse wurde 1979 von [[Leslie Valiant]] eingeführt.<br />
<br />
== Definition ==<br />
Ein Problem ist in der Klasse #P, wenn eine [[nichtdeterministische Turingmaschine]] existiert, die [[Polynomialzeit|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.<br />
<br />
== Beispiel ==<br />
Ein bekanntes Entscheidungsproblem aus NP ist das [[Erfüllbarkeitsproblem der Aussagenlogik]] (SAT):<br />
* Existiert zu einer gegebenen aussagenlogischen Formel eine erfüllende Variablenbelegung?<br />
Das zugehörige Zählproblem aus #P wird mit #SAT bezeichnet und lautet:<br />
* Wie viele erfüllende Variablenbelegungen gibt es zu einer gegebenen aussagenlogischen Formel?<br />
<br />
== Eigenschaften ==<br />
<br />
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-Turingmaschine|Orakel]]-Anfrage an ein Problem aus #P stellen dürfen, um die Sprachen in [[Polynomialzeithierarchie|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:<br />
<br />
:[[P (Komplexitätsklasse)|P]] ⊆ [[NP (Komplexitätsklasse)|NP]] ⊆ [[Polynomialzeithierarchie | PH]] ⊆ P<sup>#P</sup> ⊆ [[PSPACE]]<br />
<br />
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><br />
<br />
== Liste einiger #P-vollständiger Probleme ==<br />
* #SAT<br />
* Anzahl der [[Matching (Graphentheorie)|perfekten Matchings]] eines [[Bipartiter Graph|bipartiten Graphen]]<br />
: 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).<br />
* 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 [https://pages.cs.wisc.edu/~jyc/ Jin-Yi Cai der Webseite von Cai] als ''Talk at MIT and Brown 2008 on Holographic Algorithms''</ref><br />
* [[Permanente]] (einer 0-1-Matrix)<br />
* Anzahl der linearen Erweiterungen einer partiellen Ordnung.<br />
<br />
== Literatur ==<br />
* Leslie G. Valiant: ''The complexity of computing the permanent''. Theoretical Computer Science, 8:189-201, 1979<br />
* Graham Brightwell, Peter Winkler: Counting linear extensions, Order, Volume 8, Issue 3, Sep 1991, Pages 225 - 242, {{DOI|10.1007/BF00383444}}<br />
<br />
== Weblinks ==<br />
* {{Complexity Zoo|#P|Symbols#sharpp}}<br />
<br />
== Einzelnachweise ==<br />
<references /><br />
<br />
[[Kategorie:Komplexitätsklasse]]</div>imported>Girus