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?
5
-
$\begingroup$ This question is not research level. Should have been migrated to computer science stack exchange. $\endgroup$– Tayfun PayCommented Jan 2, 2014 at 18:14
-
2$\begingroup$ @TayfunPay given that this is an open problem, I think it should be considered research level. $\endgroup$– Sasho NikolovCommented Jan 2, 2014 at 18:30
-
1$\begingroup$ @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. $\endgroup$– David RicherbyCommented Jan 2, 2014 at 18:33
-
1$\begingroup$ @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. $\endgroup$– Kota IshiharaCommented Jan 2, 2014 at 19:00
-
1$\begingroup$ 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. $\endgroup$– Tayfun PayCommented Jan 3, 2014 at 2:56
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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 for more details on the issues surrounding complete problems for semantic classes.
answered Jan 2, 2014 at 9:30
-
1$\begingroup$ Thanks a lot for your clear and useful answer! Didn't know that RP is such a complicated class. $\endgroup$ Commented Jan 2, 2014 at 10:48
-
1$\begingroup$ Are there no approximation problems complete for RP? $\endgroup$ Commented Jan 2, 2014 at 17:21
-
3$\begingroup$ @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? $\endgroup$ Commented Jan 2, 2014 at 18:15
-
1$\begingroup$ 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. $\endgroup$ Commented Jan 2, 2014 at 18:28
-
1$\begingroup$ @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. $\endgroup$ Commented Jan 2, 2014 at 18:30