3
$\begingroup$

So according to complexity zoo, the definition of RP is:

The class of decision problems solvable by an NP machine such that

1.If the answer is 'yes,' at least 1/2 of computation paths accept.

2.If the answer is 'no,' all computation paths reject.

and the definition of PP is:

The class of decision problems solvable by an NP machine such that

1.If the answer is 'yes' then at least 1/2 of computation paths accept.

2.If the answer is 'no' then less than 1/2 of computation paths accept.

So the only difference is the behaviour of the machine when the answer is 'no'. And in Papadimitriou for RP:

There is no easy way to tell whether a machine always halts with a certified output. We informally call such classes semantic classes

So isn't it also not possible to tell whether a PP machine will always halt with a certified output? Also, don't both PP and RP accept by majority?

$\endgroup$

closed as off-topic by arnab, R B, Tsuyoshi Ito, Marzio De Biasi, Emil Jeřábek supports Monica Nov 8 '14 at 17:20

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – arnab, R B, Tsuyoshi Ito, Marzio De Biasi, Emil Jeřábek supports Monica
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 9
    $\begingroup$ RP has a large gap between the accepting and rejecting probabilities (1/2 vs. 0). With PP, by contrast, both probabilities could be exponentially close to 1/2. This single difference causes a HUGE difference in qualitative behavior: RP consists of problems that you can realistically solve (because if you repeated the computation, say, 1000 times, it would be easily to tell the difference between probability 1 and probability <=1/2). PP, by contrast, contains the NP-complete problems, and other even harder problems for which we don't expect an efficient solution to exist. $\endgroup$ – Scott Aaronson Nov 7 '14 at 19:45
  • 2
    $\begingroup$ @ScottAaronson Looks like a perfect answer to me. $\endgroup$ – john_leo Nov 7 '14 at 20:11