<p>So according to complexity zoo, the definition of RP is:</p>
<blockquote>
<p>The class of decision problems solvable by an NP machine such that</p>
<p>1.If the answer is 'yes,' at least 1/2 of computation paths accept.</p>
<p>2.If the answer is 'no,' all computation paths reject.</p>
</blockquote>
<p>and the definition of PP is:</p>
<blockquote>
<p>The class of decision problems solvable by an NP machine such that</p>
<p>1.If the answer is 'yes' then at least 1/2 of computation paths accept.</p>
<p>2.If the answer is 'no' then less than 1/2 of computation paths accept.</p>
</blockquote>
<p>So the only difference is the behaviour of the machine when the answer is 'no'.
And in Papadimitriou for RP:</p>
<blockquote>
<p>There is no easy way to tell whether a machine always
halts with a certified output. We informally call such classes semantic
classes</p>
</blockquote>
<p>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?</p>

CC BY-SA 3.0
2014-11-07T19:45:35.443Z
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
CC BY-SA 3.0
2014-11-07T20:11:17.827Z
@ScottAaronson Looks like a perfect answer to me.
john_leo
<complexity-classes><randomized-algorithms>
What is the major difference between PP and RP?
aksd
# What is the major difference between PP and RP?

(Asked by: username_0 on 2014-11-07)

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?

**Tags:** complexity-classes, randomized-algorithms

> **Comments:**
> **username_1**: 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.  
> **username_2**: @ScottAaronson Looks like a perfect answer to me.  

---

## 0 answers

