Problème dans BPP mais non connu pour être dans RP ou co-RP

Y a-t-il un exemple d'un problème naturel qui est dans BPP mais qui n'est pas connu pour être RP ou co-RP?

Déplacé mon commentaire ici après la demande de Suresh.

Un exemple d'un problème naturel pour lequel nous ne connaissons que des algorithmes qui nécessitent une erreur des deux côtés est le suivant: étant donné trois circuits algébriques, décidez si exactement deux d'entre eux sont identiques. Cela vient du fait que décider si deux circuits algébriques sont identiques est en co-RP.

Référence: voir l'article Combien de côtés à votre erreur? (2 décembre 2008) à propos de la même question sur le blog de Lance Fortnow et des commentaires ci-dessous son article pour une discussion sur le caractère naturel du problème.

Un problème sans doute plus naturel - non conçu spécifiquement pour trouver un problème qui pourrait être dans , et aussi pas si étroitement lié à un problème connu pour être dans c o R P - est fourni par le problème 2.6 de [1]: Étant donné un p premier , des entiers N et d , et une liste A de matrices d × d inversibles sur F p , le groupe généré par A a-t-il un quotient d'ordre ≥ $\mathsf{BPP} \backslash \mathsf{RP} \cup \mathsf{coRP}$$\mathsf{coRP}$$p$$N$$d$$A$$d \times d$$\mathbb{F}_{p}$$A$$\geq N$sans sous-groupes normaux abéliens? Dans [1] il est démontré que ce problème est en .$\mathsf{BPP}$

Bien que demander des quotients sans sous-groupes normaux abéliens puisse sembler excentrique, la classe des groupes sans sous-groupes normaux abéliens (parfois appelés semi-simples) est en fait assez naturelle du point de vue de la théorie de la structure des groupes. Voir [2] et ses références.

[1] L. Babai, R. Beals, A. Seress. Théorie polynomiale des groupes matriciels . STOC 2009.

[2] L. Babai, P. Codenotti, Y. Qiao. Test d'isomorphisme en temps polynomial pour les groupes sans sous-groupes normaux abéliens . À paraître, ICALP 2012.