¿Cuándo la aleatorización deja de ayudar en PSPACE?

Se sabe que agregar aleatorización de error limitado a PSPACE no agrega potencia. Es decir, BPPSAPCE = PSPACE.

Se desconoce si P = BPP, pero se sabe que . $BPP\subseteq \Sigma_2\cap \Pi_2$

Por lo tanto, es posible (mientras se conjetura que es falso) que agregar probabilidad a P agrega poder expresivo.

Mi pregunta es si sabemos (o tenemos evidencia de) el límite entre P y PSPACE donde agregar aleatorización ya no agrega poder.

Específicamente,

¿Hay algún problema que se sabe que está en (resp. ) que no se sabe que está en (resp. )? ¿Y de manera similar para vs ? $BP\Sigma_i$ $BP\Pi_i$ $\Sigma_i$ $\Pi_i$ $BPPH$ $PH$

randomness derandomization polynomial-hierarchy Shaull
fuente

BPPH = PH. xxxxxxxxxxxxx

Emil Jeřábek

@ EmilJeřábek - gracias, ¿tiene una referencia para este resultado?

Shaull

Esto es solo una relativización del teorema de Gács-Sipser-Lautemann.

Emil Jeřábek

A M \subseteq Π_{2}^{P}

$\mathrm{AM}\subseteq\Pi^P_2$

B P Σ_{i}^{P} \subseteq Π_{i + 1}^{P}

$\mathrm{BP}\Sigma^P_i\subseteq\Pi^P_{i+1}$

i \geq 1

$i\ge1$

B P Π_{i}^{P} \subseteq Σ_{i + 1}^{P}

$\mathrm{BP}\Pi^P_i\subseteq\Sigma^P_{i+1}$

Respuestas:

$\mathrm{PSPACE}$ $\mathrm{X}$ $\mathrm{P \subseteq X \subseteq PSPACE}$

\begin{aligned} B P \cdot Σ_{i}^{p} \subseteq Π_{i + 1}^{p} & and & B P \cdot Π_{i}^{p} \subseteq Σ_{i + 1}^{p} \end{aligned}

$\begin{align*} \mathrm{BP\cdot \Sigma_i^p \subseteq \Pi_{i+1}^p} &&\text{and}&& \mathrm{BP\cdot \Pi_i^p \subseteq \Sigma_{i+1}^p} \end{align*}$

A M \subseteq Π_{2}^{p}

$\mathrm{AM \subseteq \Pi_2^p}\,$

B P \cdot P H = P H

$\mathrm{BP \cdot PH = PH}$

P H \subseteq B P \cdot \oplus P .

$\mathrm{PH \subseteq BP\cdot\oplus P}.$

P H

$\mathrm{PH}$

P H \subseteq B P \cdot \oplus P

$\mathrm{PH \subseteq BP \cdot \oplus P}$

B P \cdot \oplus P = \oplus P

$\mathrm{BP \cdot \oplus P = \oplus P}$

P H \subseteq \oplus P

$\mathrm{PH \subseteq \oplus P}$

$\mathrm{PSPACE}$

Niel de Beaudrap
fuente

¡Gracias! De hecho, estaba pensando más en la jerarquía polinómica que otras clases. De hecho, esta pregunta surge del estudio de las restricciones de la lógica temporal, por lo que existe algún tipo de jerarquía entre ellas, y las clases de conteo son menos relevantes.

Shaull

Es posible que desee encontrar una versión más puntiaguda de su pregunta e intentar nuevamente. :-)

Niel de Beaudrap

B P \cdot B P P = B P P

$\mathrm{BP\cdot BPP=BPP}$

B P \cdot C = C

$\mathrm{BP}\cdot\mathcal C=\mathcal C$

C \supseteq B P P

$\mathcal C\supseteq\mathrm{BPP}$

@Emil: efectivamente, aunque una queja justa puede ser que ya hay aleatoriedad allí. Esto plantea la pregunta de si (para cualquier clase, sin importar cómo se especifique) uno puede decir si ya 'contiene aleatoriedad', pero esa es una olla de pescado mucho más complicada.

Niel de Beaudrap