¿Es

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

Si es un lenguaje de PSPACE completa, . $A$ $P^{A}=NP^{A}$

Si es un oráculo de tiempo polinómico determinista, (suponiendo ). $B$ $P^{B}\ne NP^{B}$ $P\ne NP$

es la clase de problemas de decisión análogos para y , $PP$ $\#P$ $P\subseteq PP\subseteq PSPACE$

pero ni ni es conocido. ¿Pero es cierto que $P=PP$ $PP=PSAPCE$

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

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

es un oráculo tiempo polinomial determinista, supongo que quiere decir que creemos

. (desde

)

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

Podría estar equivocado, pero déjame intentarlo: tu primera pregunta supone que la segunda contención no es estricta. En otras palabras, se supone que PP = PSPACE. En ese caso, creo que la igualdad se mantiene por el resultado que mencionaste al principio. Estoy en lo cierto? (PD: lo contrario es válido para la segunda pregunta).

MS Dousti

El teorema de Toda podría ser relevante aquí, ya que indica que uno podría doblar la diferencia entre

al oráculo

. (Pero no estoy 100% seguro al respecto.)

P

$P$

N P

$NP$

#P

$#P$

Boaz Barak, el

La respuesta a su cuarta pregunta es sí. Incluso NP ^ PSPACE está contenido en PSPACE, por lo que seguramente NP con un oráculo #P está en PSPACE.

Robin Kothari el

Como sugieren los comentarios, algunas de las preguntas formuladas en esta publicación (y algunas de las preguntas que agregó recientemente) son básicas. Muestre alguna evidencia de que realmente le importa. Consulte también meta.cstheory.stackexchange.com/questions/300/… , meta.cstheory.stackexchange.com/questions/300/… .

Tsuyoshi Ito

Respuestas:

Es un problema abierto en la teoría de la complejidad durante muchos años si colapsa, donde es la jerarquía de tiempo polinómica. También es un problema abierto para construir un oráculo para separar de . $\mathsf{PH}^{\mathsf{\#P}}$ $\mathsf{PH}$ $\mathsf{P}^{\mathsf{\#P}}$ $\mathsf{PSPACE}$

Bin Fu
fuente

Bienvenido a CSTheory.SE, @Bin Fu! :)

Daniel Apon

O tal vez estuviste aquí antes, ¡pero bienvenido de todos modos! ;)

Daniel Apon

Gracias Daniel Apon. Se sabe que PH ^ {Paridad P} colapsa. Será muy interesante si uno puede probar que PH ^ {# P} colapsa.

Bin Fu

Interesante, ¿podría proporcionar una referencia para

y el problema de su colapso, por favor?

P H^{# P}

$PH^{\#P}$

neófito

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

Si no lo interpreto mal. Teorema 4.1 (ii) está diciendo " " y . $NP^{\mathbf{C}K}=\exists \mathbf{C}K$ $coNP^{\mathbf{C}K}=\forall\mathbf{C}K$

El Lema 3.4 (c) dice "Para cualquier en la jerarquía de conteo, ". $K$ $\exists K\cup\forall K\subseteq\mathbf{C}K\subseteq\exists\mathbf{C}K\cap\forall\mathbf{C}K$

Sustitución de por , obtenemos . $K$ $P$ $PP\subseteq\exists PP\cap\forall PP$

Lo que significa que . $P^{\#P}\subseteq NP^{\#P}\cap coNP^{\#P}$

Y mantiene si la jerarquía polinómica se colapsa y la jerarquía de recuento se colapsa. $P^{\#P}=NP^{\#P}=coNP^{\#P}$

Mike Chen
fuente

La inclusión P ^ X ⊆ NP ^ X ∩ coNP ^ X para cualquier clase X está clara a partir de la definición, y no necesita el Teorema 4.1 de Torán para esto. No puedo ver por qué los colapsos de la jerarquía polinómica y la jerarquía de conteo implican P ^ # P = NP ^ # P = coNP ^ # P. ¿Puedes elaborar?

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$

=

$=$

"El colapso de la jerarquía polinómica" no necesariamente significa P = NP, y "el colapso de la jerarquía de conteo" no significa necesariamente PP = PP ^ PP.

Tsuyoshi Ito

Además, P = NP no implica P ^ # P = NP ^ # P hasta donde yo sé (pero me puede faltar algo).

Tsuyoshi Ito

Un error común en este tipo de argumentos es asumir que relativizar a un oráculo es una operación en la colección de idiomas, pero en cambio es una operación en el tipo de cálculo, que afecta drásticamente qué idiomas hay en la clase.

Derrick Stolee 01 de