Est-ce que

10

Si alors la hiérarchie s'effondre à son deuxième niveau (par le théorème de Karp-Lipton). Mais qu'en est-il de et de ? $\sf RP = NP$ $\sf NP$ $\sf coNP$

J'ai essayé de prouver que est contenu dans (l'autre sens est trivial si ) mais en vain, et je ne suis même pas sûr que ce soit vrai. $\sf BPP$ $\sf NP$ $\sf RP = NP$

Qu'est-ce que tu penses?

complexity-theory complexity-classes probabilistic-algorithms Robert777
la source

Je ne pense pas qu'il y ait une raison formelle particulière de penser ainsi (mais aucune raison non plus). Bref, je pense que c'est ouvert.

Luke Mathieson

La preuve inconditionnelle de

est un problème ouvert.

B P P \subseteq N P

$\mathbb{BPP} \subseteq \mathbb{NP}$

chazisop

3

Si nous pouvons prouver que RP est fermé sous complément alors nous pouvons dire que si RP = NP alors cela implique NP = Co-NP.

$\subseteq$

Si nous montrons que RP = BPP, votre déclaration sera correcte.

Références:

Pragya
la source

ou que RP = ZPP.

1

$\mathsf{RP=NP\implies NP\subseteq P/poly}$ $\,\subseteq\,$ P / poly (Journal of Symbolic Logic, 72 (4): 1353-171, 2007; PS ).

T ....
la source

Est-ce que

Réponses: