Problem w BPP, ale nie znany w RP lub co-RP

Czy istnieje przykład naturalnego problemu, który występuje w BPP, ale nie jest znany z RP lub ko-RP?

Przeniesiłem mój komentarz tutaj na prośbę Suresha.

Przykład naturalnego problemu, dla którego znamy tylko algorytmy wymagające błędu po obu stronach, jest następujący: biorąc pod uwagę trzy obwody algebraiczne, zdecyduj, czy dokładnie dwa z nich są identyczne. Wynika to z faktu, że decydowanie o tym, czy dwa obwody algebraiczne są identyczne, odbywa się w trybie współ-RP.

Odniesienie: patrz post Ile stron do błędu? (2 grudnia 2008 r.) Na temat tego samego pytania na blogu Lance'a Fortnowa oraz komentarzy pod jego postem w celu dyskusji na temat naturalności problemu.

Prawdopodobnie bardziej naturalne problemu - nie zaprojektowany szczególnie w celu znalezienia rozwiązania problemu może być w , jak również nie jest tak ściśle związane z problemem znanym jako być c o R P - jest dostarczony przez Problem 2.6 z [1]: Biorąc pod uwagę liczbę pierwszą p , liczby całkowite N i d oraz listę A odwracalnych macierzy d × d nad F p , czy grupa wygenerowana przez A ma iloraz rzędu ≥ $\mathsf{BPP} \backslash \mathsf{RP} \cup \mathsf{coRP}$$\mathsf{coRP}$$p$$N$$d$$A$$d \times d$$\mathbb{F}_{p}$$A$$\geq N$bez normalnych podgrup abelowych? W [1], okazuje się, że problem ten jest .$\mathsf{BPP}$

Proszenie o iloraz bez normalnych podgrup abelowych może wydawać się ekscentryczne, jednak klasa grup bez normalnych podgrup abelowych (czasami nazywana półprostymi) jest w rzeczywistości dość naturalna z punktu widzenia teorii struktury grup. Zobacz [2] i odniesienia do niego.

[1] L. Babai, R. Beals, A. Seress. Teoria wielomianów grup macierzy . STOC 2009.

[2] L. Babai, P. Codenotti, Y. Qiao. Test izomorfizmu w czasie wielomianowym dla grup bez normalnych podgrup abelowych . Aby się pojawić, ICALP 2012.