4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ This question is not research level. Should have been migrated to computer science stack exchange. $\endgroup$ – Tayfun Pay Jan 2 '14 at 18:14
  • 1
    $\begingroup$ @TayfunPay given that this is an open problem, I think it should be considered research level. $\endgroup$ – Sasho Nikolov Jan 2 '14 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 Richerby Jan 2 '14 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 Ishihara Jan 2 '14 at 19:00
  • $\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 Pay Jan 3 '14 at 2:56
9
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thanks a lot for your clear and useful answer! Didn't know that RP is such a complicated class. $\endgroup$ – Kota Ishihara Jan 2 '14 at 10:48
  • 1
    $\begingroup$ Are there no approximation problems complete for RP? $\endgroup$ – Peter Shor Jan 2 '14 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$ – Peter Shor Jan 2 '14 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$ – Sasho Nikolov Jan 2 '14 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$ – Peter Shor Jan 2 '14 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.