12
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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)$$ ? $\endgroup$ – Lieuwe Vinkhuijzen May 4 '20 at 9:01
  • $\begingroup$ That's what I meant, thanks $\endgroup$ – Ryan Williams May 5 '20 at 1:03
6
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – William Hoza May 20 '20 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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