Exemplo de algo diferente para oráculos genéricos e aleatórios?

Seja um oráculo genérico no sentido da categoria Cohen / Baire. Seja um oráculo aleatório. $G$ $R$

Existem classes de complexidade A e B com ou o contrário,

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

A pergunta foi inspirada por um comentário de Scott Aaronson .

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

Respostas:

P = UP com um genérico (assumindo P = PSPACE), mas eles são separados em relação a um oráculo aleatório.

Na outra direção, P = Promise-BPP em relação a um aleatório, mas separado em relação a um genérico. Não consigo pensar em uma classe não promissora em cima da minha cabeça.

Eu posso rastrear algumas referências, se você precisar.

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

Lance Fortnow
fonte

P = PSPACE parece uma suposição ousada;)

Bjørn Kjos-Hanssen

Para esclarecer o comentário de Bjorn: outra maneira de expressar isso é primeiro relativizar para um oráculo do PSPACE, construir um genérico e obter P = UP. Portanto, existe um oráculo genérico (relativo ao PSPACE-) que faz P = UP.

Joshua Grochow 12/09

\neq

$\neq$

Não acho que conheçamos diferenças de classe de complexidade incondicional uniforme / não promissora na forma acima (atualização: veja um exemplo da resposta de Lance Fortnow), mas a seguinte comparação de oráculos genéricos a oráculos aleatórios pode ser útil.

Um oráculo genérico é, por construção, um oráculo que satisfaz todas as propriedades que não podem ser descartadas através da fixação de um segmento inicial finito. Em certo sentido, tudo o que é necessariamente possível acontece, o que o torna muito diferente de um oráculo aleatório (embora também emule um oráculo aleatório infinitamente). $Σ^0_1$

Por exemplo, com o oráculo genérico (io significa infinitas vezes)
PSPACE ⊆ io-P
EXP ⊆ io-ZPP
EXP ^NP ⊆ io-BPP

Assim, para todo problema no PSPACE relativizado, existe um algoritmo de tempo polinomial (usando o oracle) que, para infinitos tamanhos de entrada, resolve todas as instâncias desse tamanho (e da mesma forma com ZPP e BPP com comportamento arbitrário em tamanhos de entrada "ruins") .

Como o oráculo aleatório:
IP <PSPACE
A hierarquia polinomial é infinita.

Toda função recursiva computável em tempo polinomial com um oráculo genérico é computável em tempo polinomial sem o oráculo (já que o oráculo está vazio por trechos suficientemente longos). Portanto, se P <BPP, isso também vale para o oráculo genérico, enquanto para o oráculo aleatório P = BPP.

Dmytro Taranovsky
fonte

O que você quer dizer com = io entre classes de idiomas?

Kaveh #

Então, com "P = ioPSPACE" você realmente quer dizer PSPACE ioP? Isso é bastante confuso. Por que você mudou o prefixo io para a outra classe?

\subseteq

$\subseteq$

Emil Jerabek

@Kaveh A = io B significa que existe um conjunto infinito S tal que A ⊆ SB e B ⊆ SA (onde SB é definido analogamente a io-B). No entanto, como esse uso é fora do padrão, mudei minha resposta para usar ⊆ io

Dmytro Taranovsky

@ EmilJeřábek eu substituídos = io com a norma ⊆ io

Dmytro Taranovsky

Eu sei o que isso significa para idiomas, estou perguntando o que isso significa para classes de idiomas. io-C faz sentido para uma classe C, = io, pois uma relação não parece fazer sentido, como você escreveu originalmente.

Kaveh 12/09