♯P-vollständig - ♯P-complete
Die #P-vollständigen Probleme (ausgesprochen „scharfes P vollständig“ oder „Zahl P vollständig“) bilden eine Komplexitätsklasse in der Berechnungskomplexitätstheorie . Die Probleme in dieser Komplexitätsklasse werden durch die folgenden zwei Eigenschaften definiert:
- Das Problem liegt in #P , der Klasse von Problemen, die definiert werden kann als das Zählen der Anzahl der akzeptierenden Pfade einer nichtdeterministischen Turingmaschine in polynomialer Zeit .
- Das Problem ist #P -schwer, was bedeutet, dass jedes andere Problem in #P eine Turing-Reduktion oder eine Polynomialzeitzählreduktion hat. Eine Zählreduktion ist ein Paar polynomialer Transformationen von Eingaben des anderen Problems zu Eingaben des gegebenen Problems und von Ausgaben des gegebenen Problems zu Ausgaben des anderen Problems, wodurch das andere Problem mit einer beliebigen Subroutine für das gegebene Problem gelöst werden kann Problem. Eine Turing-Reduktion ist ein Algorithmus für das andere Problem, der eine polynomielle Anzahl von Aufrufen einer Subroutine für das gegebene Problem durchführt und außerhalb dieser Aufrufe polynomiale Zeit verwendet. In einigen Fällen werden sparsame Reduktionen verwendet , eine spezifischere Art der Reduktion, die die genaue Anzahl von Lösungen beibehält.
Ein Polynomialzeitalgorithmus zum Lösen eines #P-vollständigen Problems würde, falls er existiert, das P-gegen-NP-Problem lösen, indem er impliziert, dass P und NP gleich sind. Es ist weder ein solcher Algorithmus bekannt, noch ist ein Beweis dafür bekannt, dass ein solcher Algorithmus nicht existiert.
Beispiele
Beispiele für #P-vollständige Probleme sind:
- Wie viele verschiedene Variablenzuweisungen erfüllen eine gegebene allgemeine boolesche Formel? ( #SAT )
- Wie viele verschiedene Variablenzuweisungen erfüllen eine gegebene DNF- Formel?
- Wie viele verschiedene Variablenzuweisungen erfüllen ein gegebenes 2-Erfüllbarkeitsproblem ?
- Wie viele perfekte Matchings gibt es für einen gegebenen bipartiten Graphen ?
- Welchen Wert hat die bleibende Karte einer gegebenen Matrix, deren Einträge 0 oder 1 sind? (Siehe #P-Vollständigkeit von 01-permanent .)
- Wie viele Graphfärbungen mit k Farben gibt es für einen bestimmten Graphen G ?
- Wie viele verschiedene lineare Erweiterungen gibt es für eine gegebene teilweise geordnete Menge , oder äquivalent dazu, wie viele verschiedene topologische Ordnungen gibt es für einen gegebenen gerichteten azyklischen Graphen ?
Dies sind alle notwendigerweise auch Mitglieder der Klasse #P . Betrachten Sie als Nicht-Beispiel den Fall des Zählens von Lösungen für ein 1-Erfüllbarkeitsproblem : eine Reihe von Variablen, die jeweils individuell eingeschränkt sind, aber keine Beziehungen zueinander haben. Die Lösungen können effizient gezählt werden, indem die Anzahl der Optionen für jede Variable isoliert multipliziert wird. Somit liegt dieses Problem in #P , kann aber nicht #P-vollständig sein, es sei denn, #P = FP . Dies wäre überraschend, da es implizieren würde, dass P = NP = PH .
Einfache Probleme mit hart zählenden Versionen
Einige #P-vollständige Probleme entsprechen einfachen ( polynomial time ) Problemen. Die Erfüllbarkeit einer booleschen Formel in DNF zu bestimmen ist einfach: Eine solche Formel ist genau dann erfüllbar, wenn sie eine erfüllbare Konjunktion enthält (eine, die keine Variable und ihre Negation enthält), während das Zählen der Anzahl der erfüllenden Zuweisungen #P- ist. Komplett. Darüber hinaus ist die Entscheidung über die 2-Erfüllbarkeit im Vergleich zum Zählen der Anzahl der zufriedenstellenden Aufgaben einfach. Das topologische Sortieren ist im Gegensatz zum Zählen der Anzahl der topologischen Sortierungen einfach. Ein einzelnes perfektes Matching kann in polynomieller Zeit gefunden werden, aber das Zählen aller perfekten Matchings ist #P-vollständig. Das perfekte Matching-Zählproblem war das erste Zählproblem, das einem einfachen P-Problem entsprach, das als #P-vollständig gezeigt wurde, in einem 1979 erschienenen Aufsatz von Leslie Valiant, der auch zum ersten Mal die Klasse #P und die #P-vollständigen Probleme definierte.
Annäherung
Es gibt probabilistische Algorithmen , die mit hoher Wahrscheinlichkeit gute Approximationen für einige #P-vollständige Probleme liefern. Dies ist eine der Demonstrationen der Leistungsfähigkeit probabilistischer Algorithmen.
Viele #P-vollständige Probleme haben ein randomisiertes Approximationsschema mit vollständig polynomialer Zeit oder "FPRAS", das informell mit hoher Wahrscheinlichkeit eine Approximation mit einem willkürlichen Genauigkeitsgrad in polynomialer Zeit sowohl in Bezug auf die Größe des Problems und der erforderlichen Genauigkeit. Jerrum , Valiant und Vazirani zeigten, dass jedes #P-vollständige Problem entweder ein FPRAS hat oder im Wesentlichen unmöglich zu approximieren ist; Wenn es einen Polynomialzeitalgorithmus gibt, der konsistent eine Approximation eines #P-vollständigen Problems erzeugt, das innerhalb eines Polynomverhältnisses in der Größe der Eingabe der exakten Antwort liegt, dann kann dieser Algorithmus verwendet werden, um ein FPRAS zu konstruieren.
Verweise
- ^ Brightwell, Graham R.; Winkler, Peter (1991). "Zählen von linearen Erweiterungen". Bestellen . 8 (3): 225–242. doi : 10.1007/BF00383444 ..
- ^ Leslie G. Valiant (1979). "Die Komplexität der Berechnung des Permanenten" . Theoretische Informatik . Sonst. 8 (2): 189–201. doi : 10.1016/0304-3975(79)90044-6 .
- ^ Mark R. Jerrum; Leslie G. Valiant; Vijay V. Vazirani (1986). "Zufällige Erzeugung kombinatorischer Strukturen aus einer einheitlichen Verteilung" . Theoretische Informatik . Sonst. 43 : 169–188. doi : 10.1016/0304-3975(86)90174-x .
Weiterlesen
- Vazirani, Vijay V. (2003). Approximationsalgorithmen . Berlin: Springer. ISBN 3-540-65367-8.