<p>(I'm not sure if this is research-level, but I couldn't find an answer to this question elsewhere)
The question of whether there exists an RP-complete language seems to be open, but I guess we <em>believe</em> that there exists one (because we believe that P = RP). In other words, P = RP implies that there exists an RP-complete language. Is the converse known to be true/false?</p>

CC BY-SA 3.0
2017-04-24T07:01:19.543Z
For example, if RP = NP, then RP also has a complete language.
Emil Jeřábek
CC BY-SA 3.0
2017-05-01T18:19:52.023Z
Ah. Perhaps this should be posed differently : we know that syntactic complexity classes have complete languages (that we get for free from their definitions). Is it necessarily the case that if a class (like RP) has a complete language, then it's equal to some syntactic complexity class?
Apoorva Bhagwat
CC BY-SA 3.0
2017-05-17T18:16:16.910Z
Well, if RP has a complete language $L$, then it equals the syntactic class of all languages polynomial-time reducible to $L$.
Emil Jeřábek
<cc.complexity-theory><complexity-classes>
Does the existence of an RP-complete language imply P = RP?
Apoorva Bhagwat
# Does the existence of an RP-complete language imply P = RP?

(Asked by: username_0 on 2017-04-24)

(I'm not sure if this is research-level, but I couldn't find an answer to this question elsewhere)
The question of whether there exists an RP-complete language seems to be open, but I guess we *believe* that there exists one (because we believe that P = RP). In other words, P = RP implies that there exists an RP-complete language. Is the converse known to be true/false?

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: For example, if RP = NP, then RP also has a complete language.  
> **username_0**: Ah. Perhaps this should be posed differently : we know that syntactic complexity classes have complete languages (that we get for free from their definitions). Is it necessarily the case that if a class (like RP) has a complete language, then it's equal to some syntactic complexity class?  
> **username_1**: Well, if RP has a complete language $L$, then it equals the syntactic class of all languages polynomial-time reducible to $L$.  

---

## 0 answers

