Когда рандомизация перестает помогать в PSPACE

Известно, что добавление рандомизации с ограниченной ошибкой в PSPACE не добавляет мощности. То есть BPPSAPCE = PSPACE.

Известно, что P = BPP известно, но известно, что . $BPP\subseteq \Sigma_2\cap \Pi_2$

Таким образом, возможно (хотя предполагается, что оно ложно), что добавление вероятности к P добавляет выразительную силу.

Мой вопрос заключается в том, знаем ли мы (или имеем доказательства) границу между P и PSPACE, где добавление рандомизации больше не добавляет силы.

В частности,

Существуют ли какие-либо проблемы, о которых известно, что они находятся в (соответственно, ), которые, как известно, отсутствуют в (соответственно, )? И аналогично для против ? $BP\Sigma_i$ $BP\Pi_i$ $\Sigma_i$ $\Pi_i$ $BPPH$ $PH$

randomness derandomization polynomial-hierarchy Shaull
источник

BPPH = PH. xxxxxxxxxxxxx

Эмиль Йержабек

@ EmilJeřá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}$

Эмиль Йержабек

Есть проблема с предпосылкой вашего вопроса - «когда рандомизация перестает помогать в - потому что она предполагает, что вычислительные классы такие, что образуют какую-то линейную иерархия, когда это не очевидно. $\mathrm{PSPACE}$ $\mathrm{X}$ $\mathrm{P \subseteq X \subseteq PSPACE}$

Мы можем проиллюстрировать это сравнениями между полиномиальной иерархией и счетными классами. Как указывает в комментариях Эмиль Йержабек, путем релятивизации

\begin{aligned} В п \cdot Σ_{я}^{п} \subseteq Π_{я + 1}^{п} & и & В п \cdot Π_{я}^{п} \subseteq Σ_{я + 1}^{п} \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}$

п ЧАС \subseteq В п \cdot \oplus п,

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

Ниль де Бодрап
источник

Благодарность! Я действительно думал больше о полиномиальной иерархии, чем другие классы. На самом деле, этот вопрос связан с изучением ограничений временной логики, поэтому между ними существует какая-то иерархия, и подсчет классов менее актуален.

Шаул

Возможно, вы захотите найти более точную версию своего вопроса и попробуйте снова. :-)

Ниль де Боудрап

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: конечно, хотя справедливая жалоба может быть, что там уже есть случайность. Это поднимает вопрос о том, можно ли (для любого класса, как бы он ни был указан) определить, содержит ли он уже «случайность», но это гораздо более сложный котелок с рыбой.

Ниль де Боудрап,

Когда рандомизация перестает помогать в PSPACE

Ответы: