Kiedy randomizacja przestaje pomagać w ramach PSPACE

Wiadomo, że dodanie randomizacji błędu ograniczonego do PSPACE nie dodaje mocy. Oznacza to, że BPPSAPCE = PSPACE.

Nie wiadomo, czy P = BPP, ale wiadomo, że . $BPP\subseteq \Sigma_2\cap \Pi_2$

Jest zatem możliwe (choć przypuszcza się, że jest to fałsz), że dodanie prawdopodobieństwa do P dodaje mocy ekspresyjnej.

Moje pytanie brzmi, czy znamy (lub mamy dowody) granicę między P i PSPACE, gdzie dodanie randomizacji nie dodaje już mocy.

Konkretnie,

Czy są jakieś problemy, które są znane być w (odp. ), które nie są znane być w (resp. )? I podobnie dla vs ? $BP\Sigma_i$ $BP\Pi_i$ $\Sigma_i$ $\Pi_i$ $BPPH$ $PH$

randomness derandomization polynomial-hierarchy Shaull
źródło

BPPH = PH. xxxxxxxxxxxxx

Emil Jeřábek

@ EmilJeřábek - dziękuję, czy masz odniesienie do tego wyniku?

Shaull

To tylko relatywizacja twierdzenia Gácsa-Sipsera-Lautemanna.

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

Odpowiedzi:

$\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
źródło

Dzięki! Rzeczywiście myślałem bardziej o hierarchii wielomianowej niż o innych klasach. W rzeczywistości pytanie to wynika ze studiowania ograniczeń logiki czasowej, więc istnieje między nimi jakaś hierarchia, a liczenie klas jest mniej istotne.

Shaull

Możesz wtedy znaleźć bardziej precyzyjną wersję swojego pytania i spróbować ponownie. :-)

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: na pewno, chociaż słuszna skarga może być taka, że już tam jest losowość. Rodzi to pytanie, czy (dla dowolnej klasy, jakkolwiek określono), można powiedzieć, czy już „zawiera losowość”, ale jest to znacznie bardziej skomplikowany czajnik ryb.

Niel de Beaudrap