Пример чего-то отличного для общих и случайных оракулов?

Пусть $G$ - общий оракул в смысле категории Коэна / Бэра. Пусть $R$ случайный оракул.

Существуют ли классы сложности A и B с

A^{G} = B^{G} and A^{R} \neq B^{R}

$\mathrm{A}^G=\mathrm{B}^G\quad\text{and}\quad\mathrm{A}^R\ne \mathrm{B}^R$ или наоборот,

A^{G} \neq B^{G} and A^{R} = B^{R} ?

$\mathrm{A}^G\ne\mathrm{B}^G\quad\text{and}\quad\mathrm{A}^R= \mathrm{B}^R\text{?}$

Вопрос был вдохновлен комментарием Скотта Ааронсона .

cc.complexity-theory complexity-classes Бьёрн Кьос-Хансен
источник

Ответы:

P = UP с общим (при условии P = PSPACE), но они являются отдельными относительно случайного оракула.

В другом направлении P = Promise-BPP относительно случайного, но отдельного относительно родового. Не могу придумать, что у меня не будет обещанного класса.

Я могу отследить некоторые ссылки, если вам нужно.

$P^{NP} = S^p_2$ $S^p_2 \subseteq ZPP^{NP}$

Лэнс Фортноу
источник

P = PSPACE выглядит как смелое предположение;)

Бьёрн Кьос-Ханссен

Чтобы прояснить комментарий Бьорна: еще один способ сформулировать это - сначала сделать релятивизацию к оракулу PSPACE, затем построить универсальный, а затем вы получите P = UP. Таким образом, существует (относительно PSPACE-) общий оракул, который делает P = UP.

Джошуа

\neq

$\neq$

Я не думаю, что мы знаем о безусловных различиях классов равномерной / бесперспективной сложности в приведенной выше форме (обновление: см. Ответ Ланса Фортнау для примера), но может помочь следующее сравнение общих оракулов со случайными оракулами.

Общий оракул по своей конструкции является оракулом, который удовлетворяет каждому свойству которое нельзя исключить, зафиксировав конечный начальный сегмент. В определенном смысле все, что возможно возможно, происходит, что сильно отличает его от случайного оракула (хотя он также бесконечно часто эмулирует случайный оракул). $Σ^0_1$

Например, с общим оракулом (io означает бесконечно часто)
PSPACE ⊆ io-P
EXP ⊆ io-ZPP
EXP ^NP ⊆ io-BPP

Таким образом, для каждой проблемы в релятивизированном PSPACE существует алгоритм полиномиального времени (использующий оракула), который для бесконечно многих входных размеров решает все экземпляры этого размера (и аналогично с ZPP и BPP с произвольным поведением при «плохих» входных размерах) ,

Как случайный оракул:
IP <PSPACE
. Полиномиальная иерархия бесконечна.

Каждая рекурсивная функция, вычислимая за полиномиальное время с помощью общего оракула, вычислима за полиномиальное время без оракула (поскольку оракул пуст для достаточно длинных отрезков). Таким образом, если P <BPP, то это также верно для общего оракула, а для случайного оракула P = BPP.

Дмитрий Тарановский
источник

Что вы подразумеваете под = io между классами языков?

Каве

Итак, под «P = ioPSPACE» вы на самом деле имеете в виду PSPACE ioP? Это довольно запутанно. Почему вы переместили префикс io в другой класс?

\subseteq

$\subseteq$

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

@ Kaveh A = io B означает, что существует бесконечное множество S, такое что A ⊆ SB и B ⊆ SA (где SB определяется аналогично io-B). Однако, поскольку это использование нестандартно, я изменил свой ответ, чтобы использовать ⊆ io

Дмитрий Тарановский

@ EmilJeřábek Я заменил = io стандартным ⊆ io

Дмитрий Тарановский

Я знаю, что это значит для языков, я спрашиваю, что это значит для классов языков. io-C имеет смысл для класса C, = io как отношение, кажется, не имеет смысла, как вы изначально писали.

Каве