Problem with proving that $RP subseteq NP$ : a non-deterministic TM for a language $L in RP$

Question

I'm having a small issue with wikipedia's proof that $RP subseteq NP$:

An alternative characterization of RP that is sometimes easier to use is the set of problems recognizable by nondeterministic Turing machines where the machine accepts if and only if at least some constant fraction of the computation paths, independent of the input size, accept. NP on the other hand, needs only one accepting path, which could constitute an exponentially small fraction of the paths. This characterization makes the fact that RP is a subset of NP obvious.

My problem lies in the following statement: "...accepts if and only if at least some constant fraction of the computation paths, independent of the input size, accept"
My question is: for a language $L in NP$, wouldn't it only need one computation path for the non-deterministic TM to accept? Since, if $x in L$, $P[T(x) accepts] >= 1/2$ with $T$ being the Turing machine that decides $L$.

nir shahar · Answer

Fix some $Lsubseteq RP$. Then:

if $xin L$ then $P_y[T(x,y)text{ accepts}]ge {1over2}$, therefore exists some $y$ where $T(x,y)$ accepts.
if $xnotin L$ then $P_y[T(x,y)text{ accepts}]=0$, therefore for every $y$ we have $T(x,y)$ rejects.

Thus, by definition of $NP$, $Lin NP$.
As you can see from this proof, you are correct: $NP$ requires one path while $RP$ requires at least half of the paths

Problem with proving that $RP subseteq NP$ : a non-deterministic TM for a language $L in RP$

One Answer

Add your own answers!

Ask a Question