¿Ejemplo de algo diferente para oráculos genéricos y aleatorios?

Deje que sea un oráculo genérico en el sentido de la categoría de Cohen / Baire. Deje ser un oráculo al azar. $G$ $R$

¿Hay clases de complejidad A y B con o el al revés,

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

La pregunta fue inspirada por un comentario de Scott Aaronson .

cc.complexity-theory complexity-classes Bjørn Kjos-Hanssen
fuente

Respuestas:

P = UP con un genérico (suponiendo P = PSPACE) pero están separados en relación con un oráculo aleatorio.

En la otra dirección P = Promesa-BPP en relación con un azar pero separado en relación con un genérico. No puedo pensar en una clase sin promesa fuera de mi cabeza.

Puedo localizar algunas referencias si es necesario.

Actualización: si desea una versión no prometedora, con un oráculo aleatorio (porque ) pero se separan con un oráculo genérico (ejemplo en mi artículo con Yamakami ). $P^{NP} = S^p_2$ $S^p_2 \subseteq ZPP^{NP}$

Lance Fortnow
fuente

P = PSPACE parece una suposición audaz;)

Bjørn Kjos-Hanssen

Para aclarar el comentario de Bjorn: otra forma de expresarlo es relativizar primero a un oráculo PSPACE, luego construir un genérico y luego obtener P = UP. Entonces, hay un oráculo genérico (relativo a PSPACE-) que hace que P = UP.

Joshua Grochow

Agregué un ejemplo no prometedor. También es necesario hacer algunas suposiciones porque si P

UP en el mundo no relativizado, entonces permanecen diferentes en relación con un genérico. O puedes usar el truco de Josh.

\neq

$\neq$

Lance Fortnow

No creo que sepamos diferencias de clase de complejidad incondicional / sin compromiso en la forma anterior (actualización: consulte la respuesta de Lance Fortnow para ver un ejemplo), pero la siguiente comparación de oráculos genéricos con oráculos aleatorios puede ser útil.

Un oráculo genérico es, por construcción, un oráculo que satisface todas las propiedades que no se pueden descartar arreglando un segmento inicial finito. En cierto sentido, sucede todo lo que es necesariamente posible, lo que lo hace muy diferente de un oráculo aleatorio (aunque también emula un oráculo aleatorio infinitamente a menudo). $Σ^0_1$

Por ejemplo, con el oráculo genérico (io significa infinitamente frecuente)
PSPACE ⊆ io-P
EXP ⊆ io-ZPP
EXP ^NP ⊆ io-BPP

Por lo tanto, para cada problema en el PSPACE relativizado, hay un algoritmo de tiempo polinomial (usando el oráculo) que para infinitos tamaños de entrada resuelve todas las instancias de ese tamaño (y de manera similar con ZPP y BPP con comportamiento arbitrario en tamaños de entrada 'malos') .

Como el oráculo aleatorio:
IP <PSPACE
La jerarquía polinómica es infinita.

Cada función recursiva computable en tiempo polinomial con un oráculo genérico es computable en tiempo polinomial sin el oráculo (ya que el oráculo está vacío durante períodos suficientemente largos). Por lo tanto, si P <BPP, esto también es válido para el oráculo genérico, mientras que para el oráculo aleatorio P = BPP.

Dmytro Taranovsky
fuente

¿Qué quieres decir con = io entre clases de idiomas?

Kaveh

\subseteq

$\subseteq$

@Kaveh A = io B significa que hay un conjunto infinito S tal que A ⊆ SB y B ⊆ SA (donde SB se define de forma análoga a io-B). Sin embargo, dado que este uso no es estándar, cambié mi respuesta para usar ⊆ io

Dmytro Taranovsky el

@ EmilJeřábek Reemplacé = io con el estándar ⊆ io

Dmytro Taranovsky

Sé lo que significa para los idiomas, pregunto qué significa para las clases de idiomas. io-C tiene sentido para una clase C, = io como una relación no parece tener sentido como escribió originalmente.

Kaveh