<p>An arguably more natural problem - not designed specifically for the purpose of finding a problem that might be in $\mathsf{BPP} \backslash \mathsf{RP} \cup \mathsf{coRP}$, and also not so closely related to a problem known to be in $\mathsf{coRP}$ - is furnished by Problem 2.6 of [1]: Given a prime $p$, integers $N$ and $d$, and a list $A$ of invertible $d \times d$ matrices over $\mathbb{F}_{p}$, does the group generated by $A$ have a quotient of order $\geq N$ with no abelian normal subgroups? In [1] it is shown that this problem is in $\mathsf{BPP}$.</p>

<p>While asking for quotients with no abelian normal subgroups might seem eccentric, the class of groups with no abelian normal subgroups (sometimes called semisimple) is actually fairly natural from the point of view of the structure theory of groups. See [2] and references therein.</p>

<p>[1] L. Babai, R. Beals, A. Seress. <a href="http://dx.doi.org/10.1145/1536414.1536425">Polynomial-time theory of matrix groups</a>. STOC 2009.</p>

<p>[2] L. Babai, P. Codenotti, Y. Qiao. <a href="http://people.cs.uchicago.edu/~laci/papers/icalp12.pdf">Polynomial-time isomorphism test for groups with no abelian normal subgroups</a>. To appear, ICALP 2012.</p>

CC BY-SA 3.0
2012-05-11T08:13:57.907Z
2012-05-17T20:23:47.263Z
2012-05-17T20:23:47.263Z
Joshua Grochow
<p>Moved my comment here after Suresh's request.</p>

<p>An example of a natural problem for which we only know algorithms that require error on both sides is the following: given three algebraic circuits, decide whether exactly two of them are identical. This comes from the fact that deciding whether two algebraic circuits are identical is in co-RP.</p>

<p>Reference: see the post <a href="http://blog.computationalcomplexity.org/2008/12/how-many-sides-to-your-error.html">How Many Sides to Your Error?</a> (Dec 2, 2008) about the very same question on Lance Fortnow's blog and the comments below his post for a discussion about the naturalness of the problem.</p>

CC BY-SA 3.0
2012-05-11T03:50:35.387Z
2012-05-11T03:50:35.387Z
Alessandro Cosentino
<p>Is there an example of a natural problem that's in BPP but that's not known to be in RP or co-RP?</p>

CC BY-SA 3.0
2012-05-10T02:33:35.637Z
see: http://blog.computationalcomplexity.org/2008/12/how-many-sides-to-your-error.html
Alessandro Cosentino
CC BY-SA 3.0
2012-05-11T02:12:17.753Z
@AlessandroCosentino comment -> answer ?
Suresh Venkat
<cc.complexity-theory><complexity-classes><randomness>
Problem in BPP but not known to be in RP or co-RP
arnab
# Problem in BPP but not known to be in RP or co-RP

(Asked by: username_0 on 2012-05-09)

Is there an example of a natural problem that's in BPP but that's not known to be in RP or co-RP?

**Tags:** cc.complexity-theory, complexity-classes, randomness

> **Comments:**
> **username_1**: see: http://blog.computationalcomplexity.org/2008/12/how-many-sides-to-your-error.html  
> **username_2**: @AlessandroCosentino comment -> answer ?  

---

## 2 answers

### Answer by username_1 on 2012-05-11. Score: 24 | Accepted answer

Moved my comment here after Suresh's request.

An example of a natural problem for which we only know algorithms that require error on both sides is the following: given three algebraic circuits, decide whether exactly two of them are identical. This comes from the fact that deciding whether two algebraic circuits are identical is in co-RP.

Reference: see the post [How Many Sides to Your Error?](http://blog.computationalcomplexity.org/2008/12/how-many-sides-to-your-error.html) (Dec 2, 2008) about the very same question on Lance Fortnow's blog and the comments below his post for a discussion about the naturalness of the problem.


---

### Answer by username_3 on 2012-05-11. Score: 22

An arguably more natural problem - not designed specifically for the purpose of finding a problem that might be in $\mathsf{BPP} \backslash \mathsf{RP} \cup \mathsf{coRP}$, and also not so closely related to a problem known to be in $\mathsf{coRP}$ - is furnished by Problem 2.6 of [1]: Given a prime $p$, integers $N$ and $d$, and a list $A$ of invertible $d \times d$ matrices over $\mathbb{F}\_{p}$, does the group generated by $A$ have a quotient of order $\geq N$ with no abelian normal subgroups? In [1] it is shown that this problem is in $\mathsf{BPP}$.

While asking for quotients with no abelian normal subgroups might seem eccentric, the class of groups with no abelian normal subgroups (sometimes called semisimple) is actually fairly natural from the point of view of the structure theory of groups. See [2] and references therein.

[1] L. Babai, R. Beals, A. Seress. [Polynomial-time theory of matrix groups](http://dx.doi.org/10.1145/1536414.1536425). STOC 2009.

[2] L. Babai, P. Codenotti, Y. Qiao. [Polynomial-time isomorphism test for groups with no abelian normal subgroups](http://people.cs.uchicago.edu/~laci/papers/icalp12.pdf). To appear, ICALP 2012.


---

