Randomized Complexity and Amplification

Suppose $L\in \mathrm{Z}\mathrm{P}\mathrm{P}$ and let $M$ be a zero-error expected-time machine for $L$ with $\mathbb{E}[T_x]\le p(\mathrm{\mid }x\mathrm{\mid })$. Run $M$ for exactly $2p(\mathrm{\mid }x\mathrm{\mid })$ steps and accept iff it has accepted by then. Because $M$ never errs, this truncated machine never accepts a no-instance. By [L2], $\mathbb{P}(T_x>2p(\mathrm{\mid }x\mathrm{\mid }))\le 1\mathrm{/}2$, so on yes-instances it accepts with probability at least $1\mathrm{/}2$. Thus $L\in \mathrm{R}\mathrm{P}$. By the same truncation with accept and reject swapped, also $L\in \mathrm{c}\mathrm{o}\mathrm{R}\mathrm{P}$.

Conversely, suppose $L\in \mathrm{R}\mathrm{P}\cap \mathrm{c}\mathrm{o}\mathrm{R}\mathrm{P}$. Choose an RP machine $M_{\mathrm{y}\mathrm{e}\mathrm{s}}$ for $L$ and a coRP machine $M_{\mathrm{n}\mathrm{o}}$ for $L$. On input $x$, perform independent rounds; in each round run both machines with fresh randomness. If $M_{\mathrm{y}\mathrm{e}\mathrm{s}}$ accepts, accept. If $M_{\mathrm{n}\mathrm{o}}$ rejects, reject. Otherwise repeat. By [L1], on a yes-instance the first event occurs with probability at least $1\mathrm{/}2$ and the second never occurs, while on a no-instance the second occurs with probability at least $1\mathrm{/}2$ and the first never occurs. So the algorithm is zero-error and the expected number of rounds is at most $2$.

Each round of step 1.2 uses polynomial time, so the expected runtime is polynomial. Hence $L\in \mathrm{Z}\mathrm{P}\mathrm{P}$, proving the reverse inclusion. Therefore $\mathrm{Z}\mathrm{P}\mathrm{P}=\mathrm{R}\mathrm{P}\cap \mathrm{c}\mathrm{o}\mathrm{R}\mathrm{P}$.

Let $\mu :=\mathbb{E}[S]$. By [L1] and [L2], $\mu ={\sum }_{i=1}^k\mathbb{E}[X_i]\ge 2k\mathrm{/}3$. Also [L2] and [L3] give $\mathrm{Var}(S)={\sum }_{i=1}^k\mathrm{Var}(X_i)\le k\mathrm{/}4$.

If $S\le k\mathrm{/}2$, then since $\mu \ge 2k\mathrm{/}3$ we have $\mu -S\ge k\mathrm{/}6$, so $\{S\le k\mathrm{/}2\}\subseteq \{\mathrm{\mid }S-\mu \mathrm{\mid }\ge k\mathrm{/}6\}$. Applying [L4] with $Y=S$ and $t=k\mathrm{/}6$ yields $\mathbb{P}(S\le k\mathrm{/}2)\le \mathrm{Var}(S)\mathrm{/}(k\mathrm{/}6{)}^2\le (k\mathrm{/}4)\mathrm{/}(k^2\mathrm{/}36)=9\mathrm{/}k$.

The event $S\le k\mathrm{/}2$ is exactly the event that at most half the trials are correct, so the same bound controls majority-vote error.

Let $M$ be a BPP machine for $L$. On input $x$, run $M$ independently $k:=\lceil 9q(\mathrm{\mid }x\mathrm{\mid })\rceil$ times and output the majority answer. Each run uses polynomial time and $k$ is polynomial in $\mathrm{\mid }x\mathrm{\mid }$, so the new machine is still probabilistic polynomial-time.

Fix $x$. The correctness indicators of the independent runs satisfy the hypotheses of [L2] by [L1], so the probability that the majority answer is wrong is at most $9\mathrm{/}k\le 1\mathrm{/}q(\mathrm{\mid }x\mathrm{\mid })$.

Since $x$ was arbitrary, the amplified machine has inverse-polynomial error on every input length.

Fix $\lambda >0$ and apply [L1] to the nonnegative variable $e^{-\lambda S}$. Because $e^{-\lambda t}$ decreases with $t$, we get $\mathbb{P}(S\le (1-\alpha )\mu )\le e^{\lambda (1-\alpha )\mu }\mathbb{E}[e^{-\lambda S}]$.

Since $S={\sum }_i{X}_i$, we have $e^{-\lambda S}={\prod }_i{e}^{-\lambda X_i}$. The family $(e^{-\lambda X_i}{)}_i$ is still independent, so [L3] and [L2] give $\mathbb{E}[e^{-\lambda S}]={\prod }_{i=1}^k\mathbb{E}[e^{-\lambda X_i}]=((1-p)+p{e}^{-\lambda }{)}^k\le \exp (-\mu (1-e^{-\lambda }))$, using $1-u\le e^{-u}$ with $u=p(1-e^{-\lambda })$.

Combine steps 1.1 and 1.2, and choose $\lambda$ so that $e^{-\lambda }=1-\alpha$. Then $\mathbb{P}(S\le (1-\alpha )\mu )\le \exp (\mu (-(\alpha )+(1-\alpha )\log \frac{1}{1-\alpha }))$.

Define $g(\alpha ):=-(\alpha )+(1-\alpha )\log \frac{1}{1-\alpha }+{\alpha }^2\mathrm{/}2$. Then $g(0)=0$ and $g^{\mathrm{\prime }}(\alpha )=\alpha +\log (1-\alpha )\le 0$ because $\log (1-\alpha )\le -\alpha$ for $0<\alpha <1$. Hence $g(\alpha )\le 0$, which is exactly $-(\alpha )+(1-\alpha )\log \frac{1}{1-\alpha }\le -{\alpha }^2\mathrm{/}2$. Substituting this into step 2.1 gives the claimed bound.

Let $M$ be a BPP machine for $L$. On input $x$, run $M$ independently $k$ times and output the majority answer. For the correctness indicators $X_1,\dots ,X_k$, [L1] gives a Bernoulli parameter $p_x\ge 2\mathrm{/}3$.

If the majority vote is wrong, then $X_1+\cdots +X_k\le k\mathrm{/}2\le (3\mathrm{/}4)p_{x}k$ because $p_x\ge 2\mathrm{/}3$. Thus the bad event is contained in the lower-tail event from [L2] with $\alpha =1\mathrm{/}4$, and therefore $\mathbb{P}(\text{majority is wrong on }x)\le \exp (-(1\mathrm{/}4{)}^2{p}_{x}k\mathrm{/}2)\le \exp (-k\mathrm{/}48)$.

Choose $k$ to be a sufficiently large multiple of $r(\mathrm{\mid }x\mathrm{\mid })$, for example $k=\lceil 48(\log 2)r(\mathrm{\mid }x\mathrm{\mid })\rceil$. Then step 2.1 gives error at most $2^{-r(\mathrm{\mid }x\mathrm{\mid })}$. Since $k$ is polynomial in $\mathrm{\mid }x\mathrm{\mid }$, the amplified machine is still probabilistic polynomial-time.

Let $M$ be an RP machine for $L$. Run $M$ independently $k$ times on the same input, and accept iff at least one run accepts. This remains polynomial time because $k$ independent repetitions of a polynomial-time machine still use polynomial time for fixed or polynomially bounded $k$.

If $x\mathrm{\notin }L$, then by [L1] every run rejects, so the repeated machine also rejects with probability $1$. If $x\in L$, then each run fails to accept with probability at most $1\mathrm{/}2$, and independence makes the probability that all $k$ runs fail at most $(1\mathrm{/}2{)}^k=2^{-k}$.

Thus the repeated machine keeps one-sided error and reduces the false negative probability to at most $2^{-k}$.

By [L1], for each input length $n$ there is a probabilistic polynomial-time machine $M_n$ deciding $L$ on length-$n$ inputs with error at most $2^{-(n+2)}$. Let $m(n)$ be the number of random bits used by $M_n$; this is polynomial in $n$.

For each word $x\in \{0,1{\}}^n$, let $B_x$ be the event that the random string $r\in \{0,1{\}}^{m(n)}$ makes $M_n$ err on $x$. Then $\mathbb{P}(B_x)\le 2^{-(n+2)}$. By [L2], $\mathbb{P}({\bigcup }_{x\in \{0,1{\}}^n}{B}_x)\le 2^n\cdot 2^{-(n+2)}=1\mathrm{/}4<1$. So there exists some random string $r_n$ for which no event $B_x$ occurs: that one string makes $M_n$ correct on every length-$n$ input simultaneously.

Use $a_n:=r_n$ as advice. The deterministic advice machine $D$ for input $x$ of length $n$ simulates $M_n$ on $(x,a_n)$ with the randomness tape fixed to $a_n$. By step 2.1 this simulation is correct on every length-$n$ input, and the advice length is $m(n)=\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(n)$. Therefore $L$ has polynomial advice and hence lies in $\mathrm{P}\mathrm{/}\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}$.

Fix distinct inputs $x,x^{\mathrm{\prime }}\in F$ and target outputs $y,y^{\mathrm{\prime }}\in F$. Because $x-x^{\mathrm{\prime }}\mathrm{\ne }0$, [L1] gives $a=(y-y^{\mathrm{\prime }})\mathrm{/}(x-x^{\mathrm{\prime }})$. Then $b:=y-ax$ is forced, and these values satisfy $ax+b=y$ and $a{x}^{\mathrm{\prime }}+b=y^{\mathrm{\prime }}$. Thus there is at least one pair $(a,b)$ producing the target output pair.

If $(a,b)$ and $(a^{\mathrm{\prime }},b^{\mathrm{\prime }})$ both satisfy those two equations, then subtracting them yields $(a-a^{\mathrm{\prime }})(x-x^{\mathrm{\prime }})=0$. Since $x-x^{\mathrm{\prime }}\mathrm{\ne }0$, [L1] gives $a=a^{\mathrm{\prime }}$, and then $b=b^{\mathrm{\prime }}$. So the pair from step 1.1 is unique.

The family $\mathcal{H}$ has $\mathrm{\mid }F{\mathrm{\mid }}^2$ members, and step 2.1 shows that exactly one of them maps $(x,x^{\mathrm{\prime }})$ to $(y,y^{\mathrm{\prime }})$. Therefore the probability in [L2] is $1\mathrm{/}\mathrm{\mid }F{\mathrm{\mid }}^2$, proving pairwise independence.

If $C=AB$, then the equality $Cr=(AB)r=A(Br)$ follows directly from the finite-sum definition in [L1]. So the test always accepts a correct product.

Assume $C\mathrm{\ne }AB$ and put $D:=C-AB\mathrm{\ne }0$. Then some row $d=(d_1,\dots ,d_n)$ of $D$ is nonzero. Choose the largest index $j$ with $d_j\mathrm{\ne }0$; this is possible because the row is finite.

Fix all random bits of $r$ except $r_j$. The equation $(Dr{)}_i=0$ for the chosen row has the form $d_j{r}_j=-{\sum }_{\mathrm{\ell }<j}{d}_{\mathrm{\ell }}{r}_{\mathrm{\ell }}$, because $d_{\mathrm{\ell }}=0$ for $\mathrm{\ell }>j$. By [L2], $d_j$ is invertible, so at most one value of $r_j$ can satisfy this equation. Since $r_j$ is uniform on $\{0,1\}$ and $0\mathrm{\ne }1$ in a field by [L2], the conditional probability that this row equation holds is at most $1\mathrm{/}2$. Therefore $\mathbb{P}(Dr=0)\le 1\mathrm{/}2$, and hence the acceptance probability when $C\mathrm{\ne }AB$ is at most $1\mathrm{/}2$.

Steps 1.1 and 2.1 prove the one-sided error bound for a single trial of the test. Repeating with fresh random vectors multiplies the failure probability.

If $n=0$, then $f$ is a nonzero constant polynomial and $S^0$ has the single element $()$, so $f(a)\mathrm{\ne }0$ always. Hence the vanishing probability is $0$.

If $n=1$, the statement is exactly [L2]: at most $d$ points of $S$ are roots of $f$, so the vanishing probability is at most $d\mathrm{/}\mathrm{\mid }S\mathrm{\mid }$.

Assume the claim for $n-1$ variables with $n\ge 2$. Write $f(x_1,\dots ,x_n)={\sum }_{j=0}^m{f}_j(x_2,\dots ,x_n)x_1^j$, where $m={\mathrm{deg}}_{x_1}f$ and $f_m\mathrm{\ne }0$. By [L1], the coefficient polynomial $f_m$ has total degree at most $d-m$.

Choose $(a_2,\dots ,a_n)\in S^{n-1}$ uniformly. By the induction hypothesis, the probability that $f_m(a_2,\dots ,a_n)=0$ is at most $(d-m)\mathrm{/}\mathrm{\mid }S\mathrm{\mid }$. On the complementary event, the specialized univariate polynomial $g(y):=f(y,a_2,\dots ,a_n)$ is nonzero of degree $m$, so [L2] says that for a uniform $a_1\in S$ the conditional probability $g(a_1)=0$ is at most $m\mathrm{/}\mathrm{\mid }S\mathrm{\mid }$.

Split according to the two cases in step 2.1. The total vanishing probability is at most $(d-m)\mathrm{/}\mathrm{\mid }S\mathrm{\mid }+m\mathrm{/}\mathrm{\mid }S\mathrm{\mid }=d\mathrm{/}\mathrm{\mid }S\mathrm{\mid }$. This proves the claim for every $n\ge 2$, and together with steps 1.1 and 1.2 completes the induction.

On input the representation of $f$, compute its degree bound $d$, compute the sample set $S$, choose a uniformly random point of $S^n$, evaluate $f$ at that point using [L2], and reject immediately if the value is nonzero; otherwise accept. The runtime is polynomial by the assumptions packaged into [L2].

If $f$ is the zero polynomial, every evaluation is zero, so the algorithm accepts with probability $1$. If $f$ is nonzero, [L3] gives $\mathbb{P}(f(a)=0)\le d\mathrm{/}\mathrm{\mid }S\mathrm{\mid }\le 1\mathrm{/}2$. So on no-instances the algorithm rejects with probability at least $1\mathrm{/}2$.

Step 2.1 is exactly the coRP condition from [L1]. Therefore PIT is in coRP for every representation satisfying the stated assumptions.

The hypothesis of [L1] is independence of the repeated trials. If the same random string is reused, the repeated executions become perfectly correlated instead of independent.

A perfectly correlated sequence of repetitions gives the same answer every time, so a majority vote over those repetitions agrees with one run and cannot improve its success probability. Therefore the statement is false.

Let $A:=\{x\in \{0,1{\}}^{\ast }:x\text{ begins with }1\}$. Its deterministic membership test $D(x)$ is computable in linear time. Consider the probabilistic machine that uses one fair bit $b$ and an independent string $r\in \{0,1{\}}^{n+1}$, accepts when $D(x)=1$ and either $b=1$ or $r=0^{n+1}$, and accepts when $D(x)=0$ exactly if $b=1$ and $r\mathrm{\ne }{0}^{n+1}$. Then yes-instances are accepted with probability $1\mathrm{/}2+2^{-(n+2)}$, while no-instances are accepted with probability $1\mathrm{/}2-2^{-(n+2)}$.

Step 1.1 still satisfies the PP threshold condition [L1], but the gap from $1\mathrm{/}2$ shrinks with $n$ and is not bounded below by any fixed positive constant. So the statement is false.

The hypotheses of [L1] hold with $k=25$ because $3\mathrm{/}4\ge 2\mathrm{/}3$.

Therefore the majority error probability is at most $9\mathrm{/}25$. This is a concrete instance of the general $O(1\mathrm{/}k)$ estimate.

The equality $x^2-y^2=0$ on $S\times S$ is equivalent to $x=y$ because all elements of $S$ are nonnegative rationals and squaring is injective there. Hence the roots on the grid are exactly $(0,0)$, $(1,1)$, and $(2,2)$.

So a random point of $S\times S$ makes $f$ vanish with probability $3\mathrm{/}9=1\mathrm{/}3$. This is consistent with [L2], since the total degree is $2$ and $2\mathrm{/}\mathrm{\mid }S\mathrm{\mid }=2\mathrm{/}3$. Using the random-evaluation viewpoint from [L1], this is exactly the one-sided coRP behavior asserted in [L3], because the zero polynomial would vanish on every sample point.

Consider the randomized test that accepts exactly when its first random bit is $1$. Its success probability is $1\mathrm{/}2$, so it is a legitimate witness against the statement in [L1] if repetition with the same randomness leaves that probability unchanged.

If the same random string is reused in two, ten, or one hundred repetitions, every repetition produces the same answer as the first one. So the majority outcome is still accept with probability $1\mathrm{/}2$ and reject with probability $1\mathrm{/}2$. No amplification occurs at all, and the statement is refuted.