TransWikia.com

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

Computer Science Asked by Pedro Costa on November 30, 2021

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

One Answer

Fix some $Lsubseteq RP$. Then:

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

Answered by nir shahar on November 30, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP