Quelle est la complexité du comptage du nombre de solutions d'un problème P-Space Complete? Que diriez-vous des classes plus complexes?

Je suppose qu'il s'appellerait # P-Space mais je n'ai trouvé qu'un seul article le mentionnant vaguement. Que diriez-vous de la version de comptage des problèmes EXP-TIME-Complete, NEXP-Complete ainsi que EXP-SPACE-Complete? Y a-t-il des travaux antérieurs que l'on peut citer en ce qui concerne cela ou tout autre type d'inclusion ou d'exclusion comme le théorème de Toda?

cc.complexity-theory complexity-classes counting-complexity pspace Tayfun Pay
la source

Vous demandez beaucoup en une seule question!

Tsuyoshi Ito

#PSPACE est la même que la classe de fonctions qui peut être calculée dans l'espace polynomial (FPSPACE).

Tsuyoshi Ito

@Tsuyoshi C'est vrai. Cependant, la plupart des questions posées, sinon toutes, peuvent être reformulées en une seule question générale: existe-t-il des classes de comptage pour les classes supérieures à

(comme on peut le noter dans la définition de #

) et des résultats connus s'appliquent-ils?

N P

$NP$

P

$P$

chazisop

@Tayfun Pay: je ne suis pas tout à fait sûr de ce que vous voulez dire pour les classes déterministes comme PSPACE, EXP, EXPSPACE. La notion de "nombre de solutions" est généralement étroitement liée au non-déterminisme - puisque vous pouvez alors vous interroger sur le nombre de chemins d'acceptation - ou quantificateurs / projections existentiels. Dans le cas de PSPACE, vous pouvez bien sûr utiliser la définition des quantificateurs alternés - mais vous devez ensuite spécifier les quantificateurs sur lesquels vous souhaitez compter - ou le fait que NPSPACE = PSPACE.

Joshua Grochow

Comme plusieurs commentaires l'ont mentionné, il n'est pas totalement clair ce que vous voudriez dire pour #PSPACE. Le meilleur pari serait de prendre l'analogue rembourré de #L qui est bien étudié. Comme #L est contenu dans DSPACE (log ^ 2 n), cela impliquerait que # PSPACE = PSPACE, comme @TsuyoshiIto mentionné ci-dessus. (J'ignore ici la distinction formelle immatérielle entre les problèmes de décision et les fonctions.)

Noam

Réponses:

-3

Le nombre d'affectations satisfaisantes à une formule booléenne est égal au nombre de quantifications valides de la formule. La preuve inductive est assez élégante. Donc #P = #PSpace.

Daniel pehoushek
la source

N'est-ce pas couvert par les commentaires de Tsuyoshi et Noam ci-dessus?

Huck Bennett

Est-ce vraiment ce que tu veux dire? Si #P = #PSPACE, cela n'implique-t-il pas que PSPACE

? Je ne crois pas que cela soit connu.

\subseteq

$\subseteq$

^{# P}

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

Peter Shor

@ PeterShor Je suis à peu près certain que Daniel signifie ce mathoverflow.net/a/12608/35733 . Mais ma supposition (non vérifiée) est qu'un problème # PSPACE-complet consiste à compter le nombre d'assignations satisfaisantes d'un QBF fixe, et non le nombre de quantifications satisfaisables d'un CNF donné.

Sasho Nikolov

Non, je voulais dire que le nombre de quantifications valides d'un cnf donné est égal au nombre d'assignations satisfaisantes du cnf, étant donné un ordre fixe des variables. Son très intéressant en ce que changer l'ordre des variables change les qbfs valides, mais pas le nombre total de qbfs valides.

daniel pehoushek