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.
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.
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:
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:
Da #P die Komplexitätsklasse NP enthält sind sie mindestens so schwer zu lösen.
This article uses material from the Wikipedia Deutsch article Sharp-P, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Abrufstatistik · Autoren Der Inhalt ist verfügbar unter CC BY-SA 4.0, sofern nicht anders angegeben. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Deutsch (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.