# What is the major difference between PP and RP? [closed]

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?

• 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. – Scott Aaronson Nov 7 '14 at 19:45
• @ScottAaronson Looks like a perfect answer to me. – john_leo Nov 7 '14 at 20:11