Est-ce que

Par http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf

Si est un langage complet-PSPACE, . $A$ $P^{A}=NP^{A}$

Si est un oracle à temps polynomial déterministe, (en supposant ). $B$ $P^{B}\ne NP^{B}$ $P\ne NP$

est la classe de problèmes de décision analogique pour et , $PP$ $\#P$ $P\subseteq PP\subseteq PSPACE$

mais ni ni n'est connu. Mais est-il vrai que $P=PP$ $PP=PSAPCE$

? $coNP^{\#P}=NP^{\#P}=P^{\#P}$

cc.complexity-theory complexity-classes counting-complexity open-problem oracles Mike Chen
la source

est un oracle temps polynomial déterministe, je suppose que vous voulez dire que nous croyons

. (puisque

)

B

$B$

P^{B} \neq N P^{B}

$P^B \neq NP^B$

P^{B} = P

$P^B = P$

N P^{B} = N P

$NP^B = NP$

Ramprasad

Je me trompe peut-être, mais permettez-moi de l'essayer: votre première question suppose que le deuxième confinement n'est pas strict. En d'autres termes, il suppose que PP = PSPACE. Dans ce cas, je pense que l'égalité tient au résultat que vous avez mentionné au début. Ai-je raison? (PS: L'inverse est valable pour la 2e question.)

MS Dousti

Le théorème de Toda pourrait être pertinent ici, car il indique que l'on pourrait plier la différence entre

à l' oracle

. (Mais je n'en suis pas sûr à 100%.)

P

$P$

N P

$NP$

#P

$#P$

Boaz Barak

La réponse à votre quatrième question est oui. Même NP ^ PSPACE est contenu dans PSPACE, donc sûrement NP avec un oracle #P est dans PSPACE.

Robin Kothari

Comme le suggèrent les commentaires, certaines des questions énoncées dans cet article (et certaines des questions que vous avez récemment ajoutées) sont fondamentales. Veuillez montrer des preuves que vous vous souciez vraiment. Voir également meta.cstheory.stackexchange.com/questions/300/… , meta.cstheory.stackexchange.com/questions/300/… .

Tsuyoshi Ito

Réponses:

C'est un problème ouvert dans la théorie de la complexité pendant de nombreuses années si s'effondre, où est la hiérarchie polynomiale temporelle. Il est également un problème ouvert pour construire un oracle pour séparer de . $\mathsf{PH}^{\mathsf{\#P}}$ $\mathsf{PH}$ $\mathsf{P}^{\mathsf{\#P}}$ $\mathsf{PSPACE}$

Bin Fu
la source

Bienvenue sur CSTheory.SE, @Bin Fu! :)

Daniel Apon

Ou peut-être que vous étiez ici avant, mais bienvenue quand même! ;)

Daniel Apon

Merci, Daniel Apon. On sait que PH ^ {Parité P} s'effondre. Il sera très intéressant de prouver que PH ^ {# P} s'effondre.

Bin Fu

Intéressant, pourriez-vous fournir une référence pour

et le problème de son effondrement, s'il vous plaît?

P H^{# P}

$PH^{\#P}$

néophyte

Par http://portal.acm.org/citation.cfm?id=116858

Si je ne l'interprète pas mal. Théorème 4.1 (ii) est en disant " " et . $NP^{\mathbf{C}K}=\exists \mathbf{C}K$ $coNP^{\mathbf{C}K}=\forall\mathbf{C}K$

Le lemme 3.4 (c) dit "Pour tout dans la hiérarchie de comptage, ". $K$ $\exists K\cup\forall K\subseteq\mathbf{C}K\subseteq\exists\mathbf{C}K\cap\forall\mathbf{C}K$

Remplacement de par , nous obtenons . $K$ $P$ $PP\subseteq\exists PP\cap\forall PP$

Ce qui signifie que . $P^{\#P}\subseteq NP^{\#P}\cap coNP^{\#P}$

Et est valable si la hiérarchie polynomiale s'effondre et la hiérarchie de comptage s'effondre. $P^{\#P}=NP^{\#P}=coNP^{\#P}$

Mike Chen
la source

L'inclusion P ^ X ⊆ NP ^ X ∩ coNP ^ X pour toute classe X ressort clairement de la définition, et vous n'avez pas besoin du théorème 4.1 de Torán pour cela. Je ne vois pas pourquoi les effondrements de la hiérarchie polynomiale et de la hiérarchie de comptage impliquent P ^ # P = NP ^ # P = coNP ^ # P. Peux-tu élaborer?

Tsuyoshi Ito

P = N P = c o N P

$P=NP=coNP$

P^{# P} = N P^{# P} = c o N P^{# P}

$P^{\#P}=NP^{\#P}=coNP^{\#P}$

C C P = C P

$\mathbf{C}\mathbf{C}P=\mathbf{C}P$

P P^{P P} = P P

$PP^{PP}=PP$

\exists K \cup \forall K \subseteq C K

$\exists K\cup\forall K\subseteq\mathbf{C}K$

P^{# P} \subseteq N P^{# P} \cap c o N P^{# P}

$P^{\#P}\subseteq NP^{\#P}\cap coNP^{\#P}$

\subseteq N P^{# P} \cup c o N P^{# P} \subseteq P P^{P P}

$\subseteq NP^{\#P}\cup coNP^{\#P}\subseteq PP^{PP}$

= P P = P^{# P}

$=PP=P^{\#P}$

\subseteq

$\subseteq$

=

$=$

«La hiérarchie polynomiale s'effondre» ne signifie pas nécessairement P = NP et «la hiérarchie de comptage s'effondre» ne signifie pas nécessairement PP = PP ^ PP.

Tsuyoshi Ito

De plus, P = NP n'implique pas P ^ # P = NP ^ # P pour autant que je sache (mais il me manque peut-être quelque chose).

Tsuyoshi Ito

Une erreur courante dans ce type d'arguments est de supposer que la relativisation à un oracle est une opération sur la collection de langues, mais c'est plutôt une opération sur le type de calcul, qui affecte considérablement les langues de la classe.

Derrick Stolee