<p>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 <em>some</em> leeway in computation time, or you won't get an interesting computational class.</p>

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

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

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

<p>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).</p>

CC BY-SA 3.0
2017-01-26T13:57:06.547Z
2017-01-26T13:57:06.547Z
Lieuwe Vinkhuijzen
<p>$RTIME(T(n))$ is defined as:</p>

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

<p>$x \notin L ⇒ Pr[(x) = 1] = 0$</p>

<p>Where, $ZTIME(T(n))$ defined as:</p>

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

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

<cc.complexity-theory>
$ZTIME(T(n))$ complexity $RTIME(T(n))$
Sefi Erlich
# $ZTIME(T(n))$ complexity $RTIME(T(n))$

(Asked by: username_0 on 2017-01-26)

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

**Tags:** cc.complexity-theory

---

## 1 answers

### Answer by username_1 on 2017-01-26. Score: 4 | Accepted answer

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


---

