Quando a randomização para de ajudar no PSPACE

É sabido que adicionar aleatoriedade de erro limitado ao PSPACE não adiciona energia. Ou seja, BPPSAPCE = PSPACE.

É desconhecido se notoriamente P = BPP, mas sabe-se que . $BPP\subseteq \Sigma_2\cap \Pi_2$

Assim, é possível (embora conjecturado como falso) que adicionar probabilidade a P acrescente poder expressivo.

Minha pergunta é se sabemos (ou temos evidências) da fronteira entre P e PSPACE onde a adição de randomização não adiciona mais poder.

Especificamente,

Existem problemas que são conhecidos por estar em (resp. ) que não são conhecidos por estar em (resp. )? E da mesma forma para vs ? $BP\Sigma_i$ $BP\Pi_i$ $\Sigma_i$ $\Pi_i$ $BPPH$ $PH$

randomness derandomization polynomial-hierarchy Shaull
fonte

BPPH = PH. xxxxxxxxxxxxx

Emil Jeřábek 3.0 30/04

@ EmilJeřábek - obrigado, você tem uma referência para este resultado?

Shaull

Esta é apenas uma relativização do teorema de Gács – Sipser – Lautemann.

Emil Jeřábek 3.0 30/04

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}$

Respostas:

$\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
fonte

Obrigado! Na verdade, eu estava pensando mais na hierarquia polinomial do que em outras classes. De fato, essa questão decorre do estudo de restrições da lógica temporal, portanto, existe algum tipo de hierarquia entre elas, e as classes de contagem são menos relevantes.

Shaull

Você pode encontrar uma versão mais detalhada da sua pergunta e tentar novamente. :-)

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: com certeza, embora uma queixa justa possa ser que já existe aleatoriedade lá. Isso levanta a questão de saber se (para qualquer classe, por mais especificada) se pode dizer se ela já 'contém aleatoriedade', mas essa é uma chaleira de peixe muito mais complicada.

Niel de Beaudrap