Exemple de quelque chose de différent pour les oracles génériques et aléatoires?

Soit un oracle générique au sens de la catégorie Cohen / Baire. Soit un oracle aléatoire. $G$ $R$

Existe-t-il des classes de complexité A et B avec ou le dans l'autre sens,

{UNE}^{g} = B^{g} et {UNE}^{R} \neq B^{R}

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

{UNE}^{g} \neq B^{g} et {UNE}^{R} = B^{R} ?

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

La question a été inspirée par un commentaire de Scott Aaronson .

cc.complexity-theory complexity-classes Bjørn Kjos-Hanssen
la source

Réponses:

P = UP avec un générique (en supposant P = PSPACE) mais ils sont séparés par rapport à un oracle aléatoire.

Dans l'autre sens P = Promise-BPP par rapport à un aléatoire mais séparé par rapport à un générique. Je ne peux pas penser à une classe non prometteuse du haut de ma tête.

Je peux retrouver quelques références si vous en avez besoin.

Mise à jour: si vous voulez une version non promise, avec un oracle aléatoire (car ) mais ils se séparent avec un oracle générique (exemple dans mon article avec Yamakami ). $P^{NP} = S^p_2$ $S^p_2 \subseteq ZPP^{NP}$

Lance Fortnow
la source

P = PSPACE semble être une hypothèse audacieuse;)

Bjørn Kjos-Hanssen

Pour clarifier le commentaire de Bjorn: une autre façon de le formuler est d'abord de relativiser à un oracle PSPACE, puis de construire un générique, puis vous obtenez P = UP. Il y a donc un oracle générique (relatif à PSPACE-) qui fait P = UP.

Joshua Grochow

J'ai ajouté un exemple non promis. Vous devez également faire une hypothèse car si P UP dans le monde non relativisé, ils restent différents par rapport à un générique. Ou vous pouvez utiliser l'astuce de Josh.

\neq

$\neq$

Lance Fortnow

Je ne pense pas que nous connaissions les différences inconditionnelles de classe de complexité uniforme / sans promesse dans la forme ci-dessus (mise à jour: voir la réponse de Lance Fortnow pour un exemple), mais la comparaison suivante d'oracles génériques à des oracles aléatoires peut être utile.

Un oracle générique est par construction un oracle qui satisfait chaque propriété qui ne peut pas être exclue en fixant un segment initial fini. Dans un certain sens, tout ce qui est nécessairement possible se produit, ce qui le rend très différent d'un oracle aléatoire (bien qu'il émule aussi un oracle aléatoire infiniment souvent). $Σ^0_1$

Par exemple, avec l'oracle générique (io signifie infiniment souvent)
PSPACE ⊆ io-P
EXP ⊆ io-ZPP
EXP ^NP ⊆ io-BPP

Ainsi, pour chaque problème dans le PSPACE relativisé, il existe un algorithme de temps polynomial (utilisant l'oracle) qui, pour une infinité de tailles d'entrée, résout toutes les instances de cette taille (et de la même manière avec ZPP et BPP avec un comportement arbitraire à de `` mauvaises '' tailles d'entrée) .

Comme l'oracle aléatoire:
IP <PSPACE
La hiérarchie polynomiale est infinie.

Chaque fonction récursive calculable en temps polynomial avec un oracle générique est calculable en temps polynomial sans l'oracle (puisque l'oracle est vide pour des étirements suffisamment longs). Ainsi, si P <BPP, cela vaut également pour l'oracle générique, tandis que pour l'oracle aléatoire P = BPP.

Dmytro Taranovsky
la source

Qu'entendez-vous par = io entre les classes de langues?

Kaveh

Donc, par "P = ioPSPACE", vous voulez réellement dire PSPACE ioP? C'est assez déroutant. Pourquoi avez-vous déplacé le préfixe io dans l'autre classe?

\subseteq

$\subseteq$

Emil Jeřábek

@Kaveh A = io B signifie qu'il existe un ensemble infini S tel que A ⊆ SB et B ⊆ SA (où SB est défini de manière analogue à io-B). Cependant, comme cet usage n'est pas standard, j'ai changé ma réponse pour utiliser ⊆ io

Dmytro Taranovsky

@ EmilJeřábek j'ai remplacé = io par le ⊆ io standard

Dmytro Taranovsky

Je sais ce que cela signifie pour les langues, je demande ce que cela signifie pour les classes de langues. io-C est logique pour une classe C, = io car une relation ne semble pas avoir de sens comme vous l'avez écrit à l'origine.

Kaveh