6

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?

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

1 Answers1

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.

Community
  • 1
David Richerby
  • 2,765
  • 2
  • 18
  • 28
  • 1
    Thanks a lot for your clear and useful answer! Didn't know that RP is such a complicated class. – Kota Ishihara Jan 02 '14 at 10:48
  • 1
    Are there no approximation problems complete for RP? – Peter Shor Jan 02 '14 at 17:21
  • @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 Jan 02 '14 at 17:49
  • 3
    @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 Jan 02 '14 at 18:15
  • 1
    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 Jan 02 '14 at 18:28
  • 1
    @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 Jan 02 '14 at 18:30
  • @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 Jan 02 '14 at 20:22
  • 1
    @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 Jan 02 '14 at 21:38
  • @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 Jan 02 '14 at 21:59