<p>Yes: the concept of "<strong>X</strong>-complete under <strong>Y</strong>-reductions" exists for any complexity class&nbsp;<strong>X</strong> and any class&nbsp;<strong>Y</strong> of reductions.  However, there may or may not be any complete problems under this definition, depending on what <strong>X</strong> and&nbsp;<strong>Y</strong> are. For example, it is well-known that <strong>NP</strong> has complete problems under polynomial-time, logspace and even first-order reductions, but it does not have complete problems under linear-time reductions as this would violate the time hierarchy theorem.</p>

<p>As far as I can see, it is open whether there is a class of reductions under which <strong>RP</strong> has complete problems. The issue is that it is a so-called <em>semantic class</em>: it is defined by a non-computable set of Turing machines, namely polynomial-time randomized Turing machines with the undecidable requirement that, for every input, either every path rejects or at least half accept. See <a href="https://cstheory.stackexchange.com/questions/1233/semantic-vs-syntactic-complexity-classes">this question</a> for more details on the issues surrounding complete problems for semantic classes.</p>

CC BY-SA 3.0
2014-01-02T10:48:55.667Z
Thanks a lot for your clear and useful answer! 
Didn't know that **RP** is such a complicated class.
Kota Ishihara
CC BY-SA 3.0
2014-01-02T17:21:15.940Z
Are there no approximation problems complete for RP?
Peter Shor 
CC BY-SA 3.0
2014-01-02T17:49:48.150Z
@PeterShor **RP** is a class of decision problems so an approximation problem could only be **RP**-hard. There are certainly **RP**-hard problems, since **RP** is included in **NP**.
David Richerby
CC BY-SA 3.0
2014-01-02T18:15:45.170Z
@David: you can ***weaken*** the definition of "BPP-complete" such that it makes sense for approximation problems to be "BPP-complete". You can then find lots of interesting "BPP-complete" approximation problems. People who insist that only decision problems can be be BPP-complete are leaving vast areas of interesting complexity theory completely unexplored. Such a BPP-complete approximation problem should be both BPP-hard and solvable in $\mathrm{P}^\mathrm{BPP}$. Rephrasing my question, does a similar phenomenon exist with RP?
Peter Shor 
CC BY-SA 3.0
2014-01-02T18:28:53.533Z
To add to what @PeterShor said, it is natural to consider promiseRP, for which the usual construction of complete problems should work. I think this is equivalent to what he is suggesting.
Sasho Nikolov
CC BY-SA 3.0
2014-01-02T18:30:43.913Z
@Sasho: certainly for BPP, the correct formulation in promise problems and approximation problems are equivalent. I don't know whether that is true for RP.
Peter Shor 
CC BY-SA 3.0
2014-01-02T20:22:00.647Z
@PeterShor The **X**-hard problems in **P^X** are a very natural thing to study (indeed, I've done so myself for **X=#P**) and it's perfectly possible to study them without abusing terminology by calling them "**X**-complete". I don't know if anybody has studied such problems for **RP**; it's a good question.
David Richerby
CC BY-SA 3.0
2014-01-02T21:38:09.237Z
@David: I don't understand why this is such an evil abuse of terminology. If somebody who doesn't know the relevant material already asks about **X**-complete problems, where **X** is a randomized class like **BPP**, I think a discussion of **X**-hard problems in $\mathbf{P}^\mathbf{X}$ is much more useful than the answer "as far as we know, there are no **X**-complete problems".
Peter Shor 
CC BY-SA 3.0
2014-01-02T21:59:59.277Z
@PeterShor It's an abuse of terminology because the definition of a problem being complete for a complexity class includes the requirement that the problem be in that class. But I agree that such problems are relevant to the question, if they exist.
David Richerby
CC BY-SA 3.0
2014-01-02T09:30:12.087Z
2014-01-02T09:30:12.087Z
2017-04-13T12:32:28.077Z
David Richerby
<p><strong>NP</strong>-hardness and <strong>NP</strong>-completeness play an important role in complexity theory. 
My question is, does there exist a language $L$ in <strong>RP</strong> 
to which any language $M$ in <strong>RP</strong> can be reduced in polynomial time?
We can say that such a language $L$ is "<strong>RP</strong>-complete", if exists, but I cannot find any information about this idea. Can anyone tell me about it, please?</p>

CC BY-SA 3.0
2014-01-02T18:14:12.780Z
This question is not research level. Should have been migrated to computer science stack exchange.
Tayfun Pay
CC BY-SA 3.0
2014-01-02T18:30:10.973Z
@TayfunPay given that this is an open problem, I think it should be considered research level.
Sasho Nikolov
CC BY-SA 3.0
2014-01-02T18:33:34.743Z
@TayfunPay Borderline. The literal question being asked (essentially, is there such a thing of **RP**-completeness) is not research-level but the closely related question of whether any such problems exist appears to be open so is research-level.
David Richerby
CC BY-SA 3.0
2014-01-02T19:00:41.430Z
@TayfunPay Sorry about that. Maybe I should have posted this on CS stack exchange. However, thanks to David Richerby's helpful answer and others' comments, I think now this topic has research-level value as a whole, so I want to keep it on this site. Any way, I'll be careful on which site to post a new question. Thanks.
Kota Ishihara
CC BY-SA 3.0
2014-01-03T02:56:11.977Z
If you open any good computational complexity book and read it, you will get the answer for this question. So in my opinion, it is still not research level. I have seen numerous questions down voted for the same reason.
Tayfun Pay
<cc.complexity-theory><np-hardness>
Does there exist the idea of "RP-complete", like NP-complete?
Kota Ishihara
# Does there exist the idea of "RP-complete", like NP-complete?

(Asked by: username_0 on 2014-01-02)

**NP**-hardness and **NP**-completeness play an important role in complexity theory.
My question is, does there exist a language $L$ in **RP**
to which any language $M$ in **RP** can be reduced in polynomial time?
We can say that such a language $L$ is "**RP**-complete", if exists, but I cannot find any information about this idea. Can anyone tell me about it, please?

**Tags:** cc.complexity-theory, np-hardness

> **Comments:**
> **username_1**: This question is not research level. Should have been migrated to computer science stack exchange.  
> **username_2**: @TayfunPay given that this is an open problem, I think it should be considered research level.  
> **username_3**: @TayfunPay Borderline. The literal question being asked (essentially, is there such a thing of **RP**-completeness) is not research-level but the closely related question of whether any such problems exist appears to be open so is research-level.  
> **username_0**: @TayfunPay Sorry about that. Maybe I should have posted this on CS stack exchange. However, thanks to username_3's helpful answer and others' comments, I think now this topic has research-level value as a whole, so I want to keep it on this site. Any way, I'll be careful on which site to post a new question. Thanks.  
> **username_1**: If you open any good computational complexity book and read it, you will get the answer for this question. So in my opinion, it is still not research level. I have seen numerous questions down voted for the same reason.  

---

## 1 answers

### Answer by username_3 on 2014-01-02. Score: 9

Yes: the concept of "**X**-complete under **Y**-reductions" exists for any complexity class **X** and any class **Y** of reductions. However, there may or may not be any complete problems under this definition, depending on what **X** and **Y** are. For example, it is well-known that **NP** has complete problems under polynomial-time, logspace and even first-order reductions, but it does not have complete problems under linear-time reductions as this would violate the time hierarchy theorem.

As far as I can see, it is open whether there is a class of reductions under which **RP** has complete problems. The issue is that it is a so-called *semantic class*: it is defined by a non-computable set of Turing machines, namely polynomial-time randomized Turing machines with the undecidable requirement that, for every input, either every path rejects or at least half accept. See [this question](https://cstheory.stackexchange.com/questions/1233/semantic-vs-syntactic-complexity-classes) for more details on the issues surrounding complete problems for semantic classes.

> **Comments:**
> **username_0**: Thanks a lot for your clear and useful answer!  Didn't know that **RP** is such a complicated class.  
> **username_4**: Are there no approximation problems complete for RP?  
> **username_3**: @PeterShor **RP** is a class of decision problems so an approximation problem could only be **RP**-hard. There are certainly **RP**-hard problems, since **RP** is included in **NP**.  
> **username_4**: @David: you can ***weaken*** the definition of "BPP-complete" such that it makes sense for approximation problems to be "BPP-complete". You can then find lots of interesting "BPP-complete" approximation problems. People who insist that only decision problems can be be BPP-complete are leaving vast areas of interesting complexity theory completely unexplored. Such a BPP-complete approximation problem should be both BPP-hard and solvable in $\mathrm{P}^\mathrm{BPP}$. Rephrasing my question, does a similar phenomenon exist with RP?  
> **username_2**: To add to what @PeterShor said, it is natural to consider promiseRP, for which the usual construction of complete problems should work. I think this is equivalent to what he is suggesting.  
> **username_4**: @Sasho: certainly for BPP, the correct formulation in promise problems and approximation problems are equivalent. I don't know whether that is true for RP.  
> **username_3**: @PeterShor The **X**-hard problems in **P^X** are a very natural thing to study (indeed, I've done so myself for **X=#P**) and it's perfectly possible to study them without abusing terminology by calling them "**X**-complete". I don't know if anybody has studied such problems for **RP**; it's a good question.  
> **username_4**: @David: I don't understand why this is such an evil abuse of terminology. If somebody who doesn't know the relevant material already asks about **X**-complete problems, where **X** is a randomized class like **BPP**, I think a discussion of **X**-hard problems in $\mathbf{P}^\mathbf{X}$ is much more useful than the answer "as far as we know, there are no **X**-complete problems".  
> **username_3**: @PeterShor It's an abuse of terminology because the definition of a problem being complete for a complexity class includes the requirement that the problem be in that class. But I agree that such problems are relevant to the question, if they exist.  

---

