<p>If you are happy with impying <span class="math-container">$P=RP$</span> (which implies <span class="math-container">$P = ZPP$</span>) but not <span class="math-container">$P = BPP$</span>, then there is the <a href="https://arxiv.org/abs/1901.05270" rel="noreferrer">Stoquastic PCP conjecture</a> (or its classical version, <a href="https://arxiv.org/abs/2003.13065" rel="noreferrer">a SetCSP PCP conjecture</a>).</p>

CC BY-SA 4.0
2020-05-20T22:38:10.213Z
Do these conditional proofs of P = RP also show promise-P = promise-RP? If not, that's interesting and surprising. If so, they also show P = BPP, because promise-P = promise-RP [implies](https://lance.fortnow.com/papers/files/rpvsbpp.pdf) P = BPP.
William Hoza
CC BY-SA 4.0
2020-05-04T14:34:56.110Z
2020-05-04T14:34:56.110Z
Alex Grilo
<p>I think it is "easy" to come up with an assumption that implies one but not necessarily the other... (just write down a condition that is equivalent to P=ZPP)... however, a "natural" and non-uniform assumption (e.g. some weak form of PRG) seems harder, since (for example) hitting set generators (the non-uniform thing you need for P=RP) imply pseudorandom generators (what you need for P=BPP). </p>

<hr>

<p>Just to give an idea of how annoying the problem is, here is a "natural" non-uniform condition that implies P=ZPP but (oops) also implies hitting sets, so it also implies P=BPP.</p>

<p>Say a circuit pair <span class="math-container">$(C,C')$</span> is <strong>good for length <span class="math-container">$n$</span></strong> if <span class="math-container">$C$</span> and <span class="math-container">$C'$</span> have the same number of inputs, and for every input <span class="math-container">$x$</span> of length <span class="math-container">$n$</span>,</p>

<p><span class="math-container">$(Pr_y[C(x,y)=1]&gt;2/3 \wedge Pr_y[C'(x,y)=0]=1)$</span> XOR <span class="math-container">$(Pr_y[C'(x,y)=1]&gt;2/3 \wedge Pr_y[C(x,y)=0]=1)$</span>.</p>

<p>Intuitively, these pairs can model any <span class="math-container">$RP \cap coRP = ZPP$</span> function.</p>

<p>To prove <span class="math-container">$P=ZPP$</span>, it would suffice to have for all <span class="math-container">$\epsilon &gt; 0$</span>, a polynomial time function which given <span class="math-container">$1^n$</span>, prints a set <span class="math-container">$S$</span> of <span class="math-container">$poly(n)$</span> strings of length up to <span class="math-container">$n$</span> such that for all circuit pairs <span class="math-container">$(C,C')$</span> with size <span class="math-container">$n$</span> that are good for length <span class="math-container">$m=n^{\epsilon}$</span>, and all <span class="math-container">$x$</span> of length <span class="math-container">$m$</span>, <span class="math-container">$(\exists y \in S)[C(x,y)=1 \vee C'(x,y)=1]$</span>. (This should suffice, since by definition of "good", for all <span class="math-container">$x$</span>, it cannot be that both <span class="math-container">$C$</span> and <span class="math-container">$C'$</span> have some input <span class="math-container">$y$</span> making them accept. I set <span class="math-container">$m=n^{\epsilon}$</span> to keep the condition from being too strong for other reasons.)</p>

<p>The main point is that the hitting set <span class="math-container">$S$</span> above "only" has to work for good circuit pairs. Nevertheless, this constraint isn't enough to keep from getting a full hitting set. Consider any circuit <span class="math-container">$C$</span> with <span class="math-container">$\Pr_x[C(x)=1]&gt;2/3$</span>. Write the inputs of <span class="math-container">$C$</span> over "<span class="math-container">$y$</span>-variables" instead of <span class="math-container">$x$</span>-variables. Look at the circuit pair <span class="math-container">$(0,C)$</span>, where <span class="math-container">$0$</span> is the circuit which outputs zero on all inputs <span class="math-container">$(x,y)$</span>. This pair trivially satisfies the goodness condition (<span class="math-container">$C$</span> and <span class="math-container">$0$</span> have the same behavior on all inputs <span class="math-container">$x$</span>, because they do not depend on <span class="math-container">$x$</span> at all). And if there is always an <span class="math-container">$a \in S$</span> such that <span class="math-container">$[C(x,a)=1 \vee 0(x,a) = 1]$</span> is true, then <span class="math-container">$S$</span> is just a hitting set.</p>

<p>You could try to require some "non-trivialness" condition on top of that (say that each circuit in the pair can't be trivial), but the patches I can think of could also be circumvented. </p>

<p>It would be interesting if there is a more general way to formalize this problem, so that one could convincingly show that any hitting set for anything resembling "ZPP circuits" is just a hitting set.</p>

CC BY-SA 4.0
2020-05-04T09:01:02.987Z
The brackets and braces don't match, in the definition of ``*good*''. Perhaps you meant $$(Pr_y[C(x,y)=1]>2/3 \wedge Pr_y[C^\prime(x,y)=0]=1) \text{ XOR } Pr_y(C^\prime(x,y)=1]>2/3 \wedge Pr_y[C(x,y)=0]=1)$$ ?
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2020-05-05T01:03:39.170Z
That's what I meant, thanks
Ryan Williams
CC BY-SA 4.0
2020-05-03T23:24:42.817Z
2020-05-05T01:00:44.803Z
2020-05-05T01:00:44.803Z
Ryan Williams
<p>There are assumptions that are known to imply that <span class="math-container">$P = BPP$</span>. For example, if there exists a function in <span class="math-container">$E = DTIME(2^{O(n)})$</span> that has circuit complexity <span class="math-container">$2^{\Omega(n)}$</span>, then <span class="math-container">$P = BPP$</span> [1]. Clearly, such a result would also imply that <span class="math-container">$P = ZPP$</span>.</p>

<p>Is there an assumption that is known to imply <span class="math-container">$P = ZPP$</span> but is <strong>not</strong> known to imply that <span class="math-container">$P = BPP$</span>? Alternatively, is there a reason to believe that such a result is unlikely to exist? </p>

<p>[1] Impagliazzo, Russell, and Avi Wigderson. "P= BPP if E requires exponential circuits: Derandomizing the XOR lemma." <em>Proceedings of the twenty-ninth annual ACM symposium on Theory of computing</em>. 1997.</p>

<cc.complexity-theory><complexity-classes><randomness>
Is there an assumption that implies $P=ZPP$ which is not known to imply $P=BPP$?
Morgan Shirley
# Is there an assumption that implies $P=ZPP$ which is not known to imply $P=BPP$?

(Asked by: username_0 on 2020-05-01)

There are assumptions that are known to imply that $P = BPP$. For example, if there exists a function in $E = DTIME(2^{O(n)})$ that has circuit complexity $2^{\Omega(n)}$, then $P = BPP$ [1]. Clearly, such a result would also imply that $P = ZPP$.

Is there an assumption that is known to imply $P = ZPP$ but is **not** known to imply that $P = BPP$? Alternatively, is there a reason to believe that such a result is unlikely to exist?

[1] Impagliazzo, Russell, and Avi Wigderson. "P= BPP if E requires exponential circuits: Derandomizing the XOR lemma." *Proceedings of the twenty-ninth annual ACM symposium on Theory of computing*. 1997.

**Tags:** cc.complexity-theory, complexity-classes, randomness


---

## 2 answers

### Answer by username_3 on 2020-05-03. Score: 9 | Accepted answer

I think it is "easy" to come up with an assumption that implies one but not necessarily the other... (just write down a condition that is equivalent to P=ZPP)... however, a "natural" and non-uniform assumption (e.g. some weak form of PRG) seems harder, since (for example) hitting set generators (the non-uniform thing you need for P=RP) imply pseudorandom generators (what you need for P=BPP).

---

Just to give an idea of how annoying the problem is, here is a "natural" non-uniform condition that implies P=ZPP but (oops) also implies hitting sets, so it also implies P=BPP.

Say a circuit pair $(C,C')$ is **good for length $n$** if $C$ and $C'$ have the same number of inputs, and for every input $x$ of length $n$,

$(Pr\_y[C(x,y)=1]>2/3 \wedge Pr\_y[C'(x,y)=0]=1)$ XOR $(Pr\_y[C'(x,y)=1]>2/3 \wedge Pr\_y[C(x,y)=0]=1)$.

Intuitively, these pairs can model any $RP \cap coRP = ZPP$ function.

To prove $P=ZPP$, it would suffice to have for all $\epsilon > 0$, a polynomial time function which given $1^n$, prints a set $S$ of $poly(n)$ strings of length up to $n$ such that for all circuit pairs $(C,C')$ with size $n$ that are good for length $m=n^{\epsilon}$, and all $x$ of length $m$, $(\exists y \in S)[C(x,y)=1 \vee C'(x,y)=1]$. (This should suffice, since by definition of "good", for all $x$, it cannot be that both $C$ and $C'$ have some input $y$ making them accept. I set $m=n^{\epsilon}$ to keep the condition from being too strong for other reasons.)

The main point is that the hitting set $S$ above "only" has to work for good circuit pairs. Nevertheless, this constraint isn't enough to keep from getting a full hitting set. Consider any circuit $C$ with $\Pr\_x[C(x)=1]>2/3$. Write the inputs of $C$ over "$y$-variables" instead of $x$-variables. Look at the circuit pair $(0,C)$, where $0$ is the circuit which outputs zero on all inputs $(x,y)$. This pair trivially satisfies the goodness condition ($C$ and $0$ have the same behavior on all inputs $x$, because they do not depend on $x$ at all). And if there is always an $a \in S$ such that $[C(x,a)=1 \vee 0(x,a) = 1]$ is true, then $S$ is just a hitting set.

You could try to require some "non-trivialness" condition on top of that (say that each circuit in the pair can't be trivial), but the patches I can think of could also be circumvented.

It would be interesting if there is a more general way to formalize this problem, so that one could convincingly show that any hitting set for anything resembling "ZPP circuits" is just a hitting set.

> **Comments:**
> **username_4**: The brackets and braces don't match, in the definition of ``*good*''. Perhaps you meant $$(Pr_y[C(x,y)=1]>2/3 \wedge Pr_y[C^\prime(x,y)=0]=1) \text{ XOR } Pr_y(C^\prime(x,y)=1]>2/3 \wedge Pr_y[C(x,y)=0]=1)$$ ?  
> **username_3**: That's what I meant, thanks  

---

### Answer by username_1 on 2020-05-04. Score: 6

If you are happy with impying $P=RP$ (which implies $P = ZPP$) but not $P = BPP$, then there is the [Stoquastic PCP conjecture](https://arxiv.org/abs/1901.05270) (or its classical version, [a SetCSP PCP conjecture](https://arxiv.org/abs/2003.13065)).

> **Comments:**
> **username_2**: Do these conditional proofs of P = RP also show promise-P = promise-RP? If not, that's interesting and surprising. If so, they also show P = BPP, because promise-P = promise-RP [implies](https://lance.fortnow.com/papers/files/rpvsbpp.pdf) P = BPP.  

---

