Wie komplex ist es, die Anzahl der Lösungen eines P-Space Complete-Problems zu zählen? Wie wäre es mit Klassen mit höherer Komplexität?

Ich denke, es würde # P-Space heißen, aber ich habe nur einen Artikel gefunden, der es vage erwähnt. Wie wäre es mit der Zählversion von EXP-TIME-Complete-, NEXP-Complete- und EXP-SPACE-Complete-Problemen? Gibt es frühere Arbeiten, die man in Bezug auf diese oder irgendeine Art von Einschluss oder Ausschluss wie Todas Theorem zitieren kann?

cc.complexity-theory complexity-classes counting-complexity pspace Tayfun Pay
quelle

Sie stellen viel in einer Frage!

Tsuyoshi Ito

#PSPACE entspricht der Klasse von Funktionen, die im Polynomraum (FPSPACE) berechnet werden können.

Tsuyoshi Ito

@ Tsuyoshi Das ist wahr. Die meisten der gestellten Fragen, wenn nicht alle, können jedoch als eine einzige allgemeine Frage umformuliert werden: Gibt es Zählklassen für Klassen höher als

(wie man in der Definition von #

feststellen kann ) und gelten bekannte Ergebnisse?

N P

$NP$

P

$P$

Chazisop

@Tayfun Pay: Ich bin mir nicht ganz sicher, was Sie für deterministische Klassen wie PSPACE, EXP, EXPSPACE meinen. Der Begriff "Anzahl der Lösungen" ist normalerweise eng mit dem Nichtdeterminismus verbunden - seitdem können Sie nach der Anzahl der akzeptierenden Pfade fragen - oder mit existenziellen Quantifizierern / Projektionen. Im Fall von PSPACE können Sie natürlich die Definition alternierender Quantifizierer verwenden - aber dann müssen Sie angeben, über welche Quantifizierer Sie zählen möchten - oder die Tatsache, dass NPSPACE = PSPACE.

Joshua Grochow

Wie in mehreren Kommentaren erwähnt, ist nicht ganz klar, was Sie für #PSPACE bedeuten möchten. Die beste Wette wäre, das aufgefüllte Analogon von #L zu nehmen, das gut untersucht ist. Da #L in DSPACE enthalten ist (log ^ 2 n), würde dies bedeuten, dass # PSPACE = PSPACE, wie oben erwähnt, @TsuyoshiIto. (Ich ignoriere hier die immaterielle formale Unterscheidung zwischen Entscheidungsproblemen und Funktionen.)

Noam

Antworten:

-3

Die Anzahl der erfüllenden Zuweisungen zu einer Booleschen Formel entspricht der Anzahl der gültigen Quantifizierungen der Formel. Der induktive Beweis ist sehr elegant. Also #P = #PSpace.

Daniel Pehoushek
quelle

Wird dies nicht durch die obigen Kommentare von Tsuyoshi und Noam abgedeckt?

Huck Bennett

\subseteq

$\subseteq$

^{# P}

$^{\#\mathrm{P}}$

@PeterShor Ich bin mir ziemlich sicher, dass Daniel dies meint: mathoverflow.net/a/12608/35733 . Meine (nicht überprüfte) Vermutung ist jedoch, dass ein # PSPACE-vollständiges Problem darin besteht, die Anzahl der erfüllenden Zuweisungen eines festen QBF zu zählen, nicht die Anzahl der erfüllbaren Quantifizierungen eines bestimmten CNF.

Sasho Nikolov

Nein, ich meinte, dass die Anzahl der gültigen Quantifizierungen eines gegebenen cnf gleich der Anzahl der zufriedenstellenden Zuweisungen des cnf bei einer festen Reihenfolge der Variablen ist. Es ist sehr interessant, dass durch Ändern der Reihenfolge der Variablen die gültigen qbfs geändert werden, nicht jedoch die Gesamtzahl der gültigen qbfs.

Daniel Pehoushek