$RTIME(T(n))$ is defined as:

Every language $L$ for which there is a probabilistic $TM$ $M$ running in $T(n)$ time such that $x \in L ⇒ Pr[M(x) = 1] ≥ 2/3 $

$x \notin L ⇒ Pr[(x) = 1] = 0$

Where, $ZTIME(T(n))$ defined as:

All the languages $L$ s.t. there is an expected-time $O(T (n))$ $TM$ $M$ such that for every input $x$, whenever $M$ halts on $x$, the output $M(x)$ it produces is exactly $f_{L}(x)$.

Why does $ZTIME(T(n))$ defined over expected-time and $RTIME(T(n))$ defined over the running time?


closed as off-topic by Emil Jeřábek, Jan Johannsen, Mohammad Al-Turkistany, Jeffε, András Salamon Feb 8 '17 at 12:00

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Emil Jeřábek, Jan Johannsen, Mohammad Al-Turkistany, Jeffε, András Salamon
If this question can be reworded to fit the rules in the help center, please edit the question.


Because if you define Zero-error time as running in strictly $O(T(n))$, then you would just get deterministic $O(T(n))$-time. (Why? Because then every choice of random bits suffices, so just pick the string $0^{T(n)}$ and simulate the machine to get the right answer). In particular, if you define $ZPP$ as zero-error with running time strictly bounded by a polynomial you just get your good old class $ZPP=P$. Simply put, if you have randomness but zero error, then you have to allow for some leeway in computation time, or you won't get an interesting computational class.

By contrast, you are free to define $RP$ as operating in expected polynomial time instead of strictly bounded time, but it won't change anything; you just get the normal class $RP$ (Why? Excercise!)

Hence $ZPP$ is to $RP$ a bit like $P$ is to $NP$ because if you take $P$ and $NP$ and say

  • The running time is expected polynomial time instead of strictly polynomially bounded, and
  • The error is one-sided bounded by $\frac{1}{3}$ instead of one-sided unbounded

then you obtain the classes $ZPP$ and $RP$. According to Arora and Barak, that makes the theorem $ZPP=RP\cap coRP$ surprising, because the analogous statement, $P=NP\cap coNP$, is not known (or expected).


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