Kapan pengacakan berhenti membantu dalam PSPACE

Diketahui bahwa menambahkan pengacakan kesalahan terbatas ke PSPACE tidak menambah daya. Yaitu, BPPSAPCE = PSPACE.

Tidak diketahui apakah P = BPP, tetapi diketahui bahwa . $BPP\subseteq \Sigma_2\cap \Pi_2$

Dengan demikian, adalah mungkin (meskipun diduga salah) bahwa menambahkan probabilitas ke P menambah daya ekspresif.

Pertanyaan saya adalah apakah kita tahu (atau memiliki bukti) perbatasan antara P dan PSPACE di mana menambahkan pengacakan tidak lagi menambah kekuatan.

Secara khusus,

Apakah ada masalah yang diketahui berada di (resp. ) yang tidak diketahui berada di (resp. )? Dan juga untuk vs ? $BP\Sigma_i$ $BP\Pi_i$ $\Sigma_i$ $\Pi_i$ $BPPH$ $PH$

randomness derandomization polynomial-hierarchy Shaull
sumber

BPPH = PH. xxxxxxxxxxxxx

Emil Jeřábek 3.0

@ EmilJeřábek - terima kasih, apakah Anda memiliki referensi untuk hasil ini?

Shaull

Ini hanyalah relativisasi dari teorema Gács – Sipser – Lautemann.

Emil Jeřábek 3.0

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

Jawaban:

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

Terima kasih! Saya memang lebih memikirkan hierarki polinomial daripada kelas-kelas lain. Sebenarnya, pertanyaan ini bermula dari mempelajari pembatasan logika temporal, jadi ada semacam hierarki di antara mereka, dan penghitungan kelas kurang relevan.

Shaull

Anda mungkin ingin menemukan versi pertanyaan Anda yang lebih runcing, dan coba lagi. :-)

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: tentu saja, meskipun keluhan yang adil mungkin sudah ada keacakan di sana. Hal ini menimbulkan pertanyaan apakah (untuk kelas mana pun, bagaimanapun ditentukan) seseorang dapat mengatakan apakah sudah 'mengandung keacakan', tapi itu adalah ketel ikan yang jauh lebih rumit.

Niel de Beaudrap