♯P

Im Computerkomplexitätstheorie, die Komplexitätsklasse #P (ausgesprochen "scharfe p" oder manchmal "Nummer p" oder "Hash P") ist der Satz der Probleme zählen in Verbindung mit Entscheidungsprobleme im Set Np. Formeller, #P ist die Klasse von Funktionsproblemen des Formulars "Berechnung f(x)", wo f ist die Anzahl der Akzeptanzwege von a Nichtdeterministische Turing -Maschine einlaufen Polynomzeit. Im Gegensatz zu den meisten bekannten Komplexitätsklassen ist es keine Klasse von Entscheidungsprobleme aber eine Klasse von Funktionsprobleme. Die schwierigsten repräsentativen Probleme dieser Klasse sind #P-Complete.

Beziehung zu Entscheidungsproblemen

Ein Np Entscheidungsproblem stammt oft von der Form "Gibt es Lösungen, die bestimmte Einschränkungen erfüllen?" Zum Beispiel:

Gibt es Untergruppen einer Liste von Ganzzahlen, die sich auf Null summieren? (Summenproblem)
Sind da welche Hamiltonsche Zyklen in einem gegebenen Graph mit Kosten weniger als 100? (Problem mit reisenden Verkäufern)
Gibt es variable Zuordnungen, die eine gegebene Befriedigung erfüllen? CNF (Konjunktive Normalform) Formel? (Boolesche Zufriedenheitsproblem oder sa)
Hat ein univariiertes reales Polynom positive Wurzeln? (Wurzelfindung)

Die entsprechende #P Funktionsprobleme fragen "wie viele" und nicht "gibt es irgendwelche". Zum Beispiel:

Wie viele Teilmengen einer Liste von Ganzzahlen summieren sich auf Null?
Wie viele Hamiltonsche Zyklen in einem bestimmten Diagramm haben weniger als 100 gekostet?
Wie viele variable Zuordnungen erfüllen eine bestimmte CNF -Formel?
Wie viele Wurzeln eines univariaten realen Polynoms sind positiv?

Formale Definitionen

#P wird formell wie folgt definiert:

#P ist der Satz aller Funktionen

{\ displaystyle f: \ {0,1 \}^{*} \ to \ mathbb {n}}

so dass es eine Polynomzeit gibt Nichtdeterministische Turing -Maschine

{\ displayStyle m}

so dass für alle

{\ displaystyle x \ in \ {0,1 \}^{*}}

,

{\ displayStyle f (x)}

entspricht der Anzahl der Akzeptieren von Zweigen in

{\ displayStyle m}

Berechnungsdiagramm auf

{\ displayStyle x}

.^[1]

#P kann auch äquivalent in Bezug auf einen Verifer definiert werden. Ein Entscheidungsproblem ist in Np Wenn es eine Polynom-Zeit-Überprüfung gibt Zertifikat zu einer bestimmten Probleminstanz - das heißt, Np fragt, ob es einen Mitgliedschaftsnachweis für die Eingabe gibt, die in der Polynomzeit auf Korrektheit überprüft werden kann. Die Klasse #P fragt wie viele Es gibt Zertifikate dort für eine Probleminstanz, die in der Polynomzeit auf Korrektheit überprüft werden kann.^[1] In diesem Zusammenhang, #P wird wie folgt definiert:

#P ist der Satz von Funktionen

{\ displaystyle f: \ {0,1 \}^{*} \ to \ mathbb {n}}

so dass es ein Polynom gibt

{\ displayStyle p: \ mathbb {n} \ to \ mathbb {n}}

und eine Polynomzeit deterministische Turing -Maschine

{\ displayStyle v}

, genannt der Verifizierer, so dass für jeden

{\ displaystyle x \ in \ {0,1 \}^{*}}

,

{\ displayStyle f (x) = {\ big |} {\ big \ {} y \ in \ {0,1 \}^{p (| x |)}: v (x, y) = 1 {\ big \}} {\ Big |}}

.^[2] (Mit anderen Worten,

{\ displayStyle f (x)}

entspricht der Größe des Satzes, der alle Zertifikate der Polynomgröße enthält).

Geschichte

Die Komplexitätsklasse #P wurde zuerst definiert von Leslie Valiant In einem Artikel von 1979 über die Berechnung der dauerhaft von a quadratische Matrix, in dem er das bewiesen hat permanent ist #P-Complete.^[3]

Larry Stockmeyer hat das für jedes #P -Problem bewiesen ${\ displayStyle p}$ Es gibt a Randomisierter Algorithmus Verwenden eines Orakels für SAT, das eine Instanz enthielt ${\ displayStyle a}$ von ${\ displayStyle p}$ und ${\ displayStyle \ Epsilon> 0}$ kehrt mit hoher Wahrscheinlichkeit eine Zahl zurück ${\ displayStyle x}$ so dass ${\ displayStyle (1- \ epsilon) p (a) \ leq x \ leq (1+ \ epsilon) p (a)}$ .^[4] Die Laufzeit des Algorithmus ist polynomisch in ${\ displayStyle a}$ und ${\ displayStyle 1/\ Epsilon}}$ . Der Algorithmus basiert auf dem übrig gebliebenes Hash Lemma.

Siehe auch

Quantum_computing#relation_to_computability_and_complexity_theory- Untersuchung eines Berechnungsmodells

Verweise

^ ^a ^b Barak, Boaz (Frühjahr 2006). "Komplexität des Zählens" (PDF). Informatik 522: Computerkomplexität. Princeton Universität.
^ Arora, Sanjeev; Barak, Boaz (2009). Rechenkomplexität: ein moderner Ansatz. Cambridge University Press. p. 344. ISBN 978-0-521-42426-4.
^ Leslie G. Valiant (1979). "Die Komplexität der Berechnung der Permanenten". Theoretische Informatik. Elsevier. 8 (2): 189–201. doi:10.1016/0304-3975 (79) 90044-6.
^ Stockmeyer, Larry (November 1985). "Bei Approximationsalgorithmen für #P" (PDF). Siam Journal über Computing. 14 (4): 849. doi:10.1137/0214060. Archiviert von das Original (PDF) auf 2009.

Externe Links

Komplexitätszoo: Klasse #P

[Barak-Counting-1] Barak, Boaz (Frühjahr 2006). "Komplexität des Zählens" (PDF). Informatik 522: Computerkomplexität. Princeton Universität.

[2] Arora, Sanjeev; Barak, Boaz (2009). Rechenkomplexität: ein moderner Ansatz. Cambridge University Press. p. 344. ISBN 978-0-521-42426-4.

[3] Leslie G. Valiant (1979). "Die Komplexität der Berechnung der Permanenten". Theoretische Informatik. Elsevier. 8 (2): 189–201. doi:10.1016/0304-3975 (79) 90044-6.

[4] Stockmeyer, Larry (November 1985). "Bei Approximationsalgorithmen für #P" (PDF). Siam Journal über Computing. 14 (4): 849. doi:10.1137/0214060. Archiviert von das Original (PDF) auf 2009.

[1]

[2]

[3]

[4]

Wichtig Komplexitätsklassen (mehr)
Als machbar angesehen	Dlogime AC⁰ Acc⁰ TC⁰ L Sl Rl Nl NC SC CC P P-Complete Zpp RP BPP BQP APX FP
Mutmaßlich unmöglich	HOCH Np NP-Complete Np-harte Co-NP CO-NP-Complete BIN QMA PH ⊕p Pp #P #P-Complete IP PSPACE PSPACE-Complete
Als nicht realisierbar	Nachfolger Nexptime Expace 2-Exptime Elementar Pr R BETREFFEND ALLE
Klassenhierarchien	Polynomhierarchie Exponentielle Hierarchie Grzegorczyk Hierarchie Arithmetische Hierarchie Boolesche Hierarchie
Familien von Klassen	Time Ntzeit DSpace Nspace Probabilistisch prüfbarer Beweis Interaktives Proof -System

♯P

Inhalt