2
$\begingroup$

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$.

$\endgroup$

1 Answer 1

4
$\begingroup$

Fix some $L\subseteq RP$. Then:

  1. if $x\in L$ then $P_y[T(x,y)\text{ accepts}]\ge {1\over2}$, therefore exists some $y$ where $T(x,y)$ accepts.
  2. if $x\notin 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$, $L\in NP$.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.