# Is there an assumption that implies $P=ZPP$ which is not known to imply $P=BPP$?

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

 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.

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.

• 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)$$ ? May 4, 2020 at 9:01
• That's what I meant, thanks May 5, 2020 at 1:03

If you are happy with impying $$P=RP$$ (which implies $$P = ZPP$$) but not $$P = BPP$$, then there is the Stoquastic PCP conjecture (or its classical version, a SetCSP PCP conjecture).

• 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 P = BPP. May 20, 2020 at 22:38