10
$\begingroup$

$\mathsf{BPP}$ and $\mathsf{ZPP}$ are two of basic probabilistic complexity classes.

$\mathsf{BPP}$ is the class of languages decided by probabilistic polynomial-time Turing algorithms where the probability of algorithm returning an incorrect answer is bounded, i.e. the error probability is at most $\frac{1}{3}$ (for both YES and NO instances).

On the other hand, $\mathsf{ZPP}$ algorithms can be viewed as those probabilistic algorithms which never return an incorrect answer, whenever they return an answer it is correct. However their running-time is not bounded by a polynomial, they run in expected polynomial.

Let $\mathsf{ZPTime}(f)$ be the class of language decided by probabilistic algorithms with zero error probability and expected running-time $f$. These are also referred to as Las Vegas algorithms and $\mathsf{ZPP} = \mathsf{ZPTime}(n^{O(1)})$.

My question is what is best know simulation of $\mathsf{BPP}$ algorithms using Las Vegas algorithms? Can we simulate them in subexponential expected time? Is there any known improvement over the trivial brute-force simulation which takes exponential time?

More formally, do we know if $\mathsf{BPP} \subseteq \mathsf{ZPTime}(2^{O(n^{\epsilon})})$ or $\mathsf{BPP} \subseteq \mathsf{ZPTime}(2^{n-n^{\epsilon}})$ for some $\epsilon>0$?

$\endgroup$
  • 3
    $\begingroup$ What is n, the length of the input? Why can we accept in $2^n$? $\endgroup$ – domotorp Mar 27 '13 at 15:11
  • 1
    $\begingroup$ $2^{\mathrm{poly}(n)-n^\epsilon}$ is the same thing as $2^{\mathrm{poly}(n)}$. $\endgroup$ – Emil Jeřábek supports Monica Mar 28 '13 at 12:17
  • 2
    $\begingroup$ I find the question quite interesting. I edited the question to make to make it more readable and precise. Feel free to edit further. ps: I am guessing that you probably wanted to take into account the polynomially many random bits used by the BPP algorithm as a parameter for the simulation time but as Emil points out what you wrote gives $2^{poly(n)}$. If you want that you have to replace BPP with particular class of bounded error probabilistic algorithms that have a parameter for the number of random bits used by the algorithm. $\endgroup$ – Kaveh Mar 28 '13 at 22:47
  • $\begingroup$ You can ask if we can simulate a BPP algorithm which uses $r(n)$ random bits in $\mathsf{ZPTime}(2^{r(n)-n^\epsilon}n^{O(1)})$ since the brute-force simulation runs in $2^{r(n)}n^{O(1)}$ time. $\endgroup$ – Kaveh Mar 28 '13 at 22:52
13
$\begingroup$

First, observe that if $\mathsf{BPP} \subseteq \mathsf{ZPTIME}[2^{n^{c}}]$ for some constant $c$, then $\mathsf{BPP} \neq \mathsf{NEXP}$. (Proof by nondeterministic time hierarchy.) So proving such an inclusion would be significant, not just because it's an improved simulation but also would yield the first progress on randomized time lower bounds in decades.

Next, consider the class $\mathsf{PromiseBPP}$, for which the following problem is "$\mathsf{PromiseBPP}$-hard":

Circuit Approximation Probability Problem (CAPP): Given a circuit $C$, output the acceptance probability of $C$ to within a $1/6$ additive factor.

Results of Impagliazzo, Kabanets, and Wigderson 2002 imply that a $2^{n^{\varepsilon}}$ time zero-error algorithm for CAPP (where $n$ is the size of $C$) would imply $\mathsf{NEXP} \not\subset \mathsf{P/poly}$. In STOC'10, I extended this to show: supposing for every $C$ with $k$ input bits and $n$ size, one can compute CAPP nondeterministically (so, zero-error suffices) in $2^{k-\omega(\log k)}\mathrm{poly}(n)$ time, then $\mathsf{NEXP} \not\subset \mathsf{P/poly}$. That is, there are certainly problems computable with two-sided-error randomness, for which zero-error algorithms that even mildly beat exhaustive search would imply circuit lower bounds. I believe this should be interpreted as a possible method for proving lower bounds; your mileage may vary.

Notice that even proving $\mathsf{RP} \subseteq \mathsf{ZPTIME}[2^{n^{\varepsilon}}]$ is also open, and proving that would also imply lower bounds: by Kabanets and Impagliazzo 2004, if polynomial identity testing (a $\mathsf{coRP}$ problem) is in $\mathsf{ZPTIME}[2^{n^{\varepsilon}}]$ for all $\varepsilon > 0$, then we have lower bounds for either the Permanent or $\mathsf{NEXP}$. Recently (upcoming in STOC'13), I proved unconditionally that either $\mathsf{BPP} \subseteq \mathsf{ioZPTIME}[2^{n^{\varepsilon}}]/n^{\varepsilon}$ or $\mathsf{RTIME}[2^n]$ has $n^c$ size circuits, building on the "easy witness" method of Kabanets. This implies two things:

  1. There is a $c$ such that for all $\varepsilon > 0$, $\mathsf{RP}$ is unconditionally in $\mathsf{ioZPTIME}[2^{n^{\varepsilon}}]/n^c$ -- this is about the best unconditional derandomization of $\mathsf{RP/BPP}$ in $\mathsf{ZPP}$ that we know so far.

  2. To start getting interesting subexponential simulations of $\mathsf{BPP}$, you "only" have to assume $\mathsf{RTIME}[2^n]$ doesn't have fixed-polynomial-size circuits.

$\endgroup$
  • $\begingroup$ Thanks to Niel for taking the time to make my response legible :) $\endgroup$ – Ryan Williams Apr 1 '13 at 20:00
  • 2
    $\begingroup$ Ryan, I think I am about to ask a very stupid question, but here I go: in your first sentence, why do you need "for all $\epsilon$"? Doesn't BPP subset of ZPTIME(2^(n^c)) for some c fixed imply BPP subset of RTIME(2^(n^c)) and therefore NTIME(2^(n^c)), so BPP is not equal to NEXP or otherwise NTIME(2^(2n^c)) is a subset of NTIME(2^(n^c))? $\endgroup$ – Sasho Nikolov Apr 1 '13 at 22:49
  • 1
    $\begingroup$ Not stupid at all -- indeed, $BPP \subseteq NTIME(2^{n^c})$ for some $c$ is enough for $BPP \neq NEXP$, thanks for pointing that out. Subexponential time algorithms are necessary for the other consequences, though. $\endgroup$ – Ryan Williams Apr 2 '13 at 17:14
  • $\begingroup$ Ryan: If I wanted to understand your paper what book/papers on circuit complexity do you recommend to be familiar with? $\endgroup$ – T.... Apr 3 '13 at 5:24
  • $\begingroup$ Hi Arul, luckily Bill Gasarch asked me this question a while back, and put up the following webpage of links: cs.umd.edu/~gasarch/ryan/ryan.html $\endgroup$ – Ryan Williams Apr 4 '13 at 21:26
8
$\begingroup$

It depends on what assumptions you are willing to make.

Under certain hardness assumptions, namely $E \not\subseteq SIZE(2^{\varepsilon n})$, you get that $P = BPP$. This in particular implies that $BPP = ZPP$, and therefore that every language $L \in BPP$ is accepted by a Las Vegas machine (see "P=BPP unless E has Subexponential Circuits: Derandomizing the XOR Lemma", by Impagliazzo and Wigderson).

You can also make a milder hardness assumption, namely, that $ZPE \not\subseteq \rm{io-DTIME}(2^{\varepsilon n})$, and get that $BPP = ZPP$ (see Lemma 46 in "In search of an easy witness: Exponential time vs. probabilistic polynomial time" by Impagliazzo, Kabanets and Wigderson).

$\endgroup$
4
$\begingroup$

Barring any advances in derandomization, it seems to me as though the requirement that the Las Vegas Machine makes no mistakes is crucial, so that there is little to no benefit to having randomness at all in this case.

For a BPP language $L$ decided by a suitable algorithm $A$, which acts on inputs $x \in \{0,1\}^n$ and a random string $r \in \{0,1\}^{N(n)}$ representing its random choices, the zero-error criterion implies that the Las Vegas machine must ascertain for certain which of the two cases $$\Pr_r(\text{$A$ accepts $(x,r)$}) \geqslant \tfrac{2}{3} \quad\text{or}\quad \Pr_r(\text{$A$ accepts $(x,r)$}) \leqslant \tfrac{1}{3}$$ holds. If we are given no further information about $A$, then this is essentially an oracle promise problem: given an oracle $A'$ computing $A'(r) = A(x,r)$, and given the promise that $A'$ yields one output $a \in \{0,1\}$ for at least twice as many inputs as the opposite output $1-a$, determine which output is more common.

Although the Las Vegas Machine may use random techniques, if we are indeed forced to treat $A'$ as an oracle, we can see that the only strategy available to a Las Vegas machine is to take a relatively thorough (though not exhaustive) survey of the random strings $r$, to see what answer is given for each. It can only be sure if it finds more than $2^{N(n)}\!/3$ distinct strings $r$ which all give rise to the same output; otherwise, with small (but non-zero!) probability, it may be unlucky and obtain a non-representative sample of the possible outputs. To obtain zero error, it must sample at least $2^{N(n)}\!/3$ inputs $r$.

Because the Las Vegas machine must inspect at least a constant fraction of all of the possible random strings $r$, asymptotically we're no better off than if we deterministically tested all possible random strings. We get no asymptotic advantage in simulating BPP algorithms randomly in a zero-error setting, beyond what we can do deterministically by brute-force.

Note that this same argument gives rise to an oracle separation between BPP and ZPP, i.e. there is an oracle $A$ such that $$\mathsf{ZPP}^A \subsetneqq \mathsf{BPP}^A$$ because the ZPP algorithm takes exponential time, while a BPP algorithm can solve the question about the oracle in a single query and succeed with bounded error. However, it doesn't tell you any more than what you suspected already (that the simulation overhead may be worse than polynomial) nor that the asymptotics are just as bad as a naive deterministic simulation.

$\endgroup$
  • $\begingroup$ correct me if i am wrong: you are giving some intuitive reasoning why derandomization seems impossible, but we know that under some reasonable assumptions BPP, ZPP, and P are all the same thing. so that intuition is not necessarily any good $\endgroup$ – Sasho Nikolov Mar 28 '13 at 15:32
  • 1
    $\begingroup$ Not at all. Derandomization would presumably be an insight into how to simulate BPP by P, wouldn't it? I'm just describing how, if he wants unconditional results which do not exploit the structure of the algorithm itself, he may as well perform a deterministic simulation as a zero-error randomized one. Or is there something wrong with this explanation? $\endgroup$ – Niel de Beaudrap Mar 28 '13 at 15:47
  • 1
    $\begingroup$ i think all you are saying is that the naive brute force simulation of BPP by ZPP is not much faster than the naive brute force simulation of BPP by P. but i cannot see what that is supposed to show. to me this is like someone asking 'what is the fastest algorithm for finding a maximum matching' and getting as an answer 'well, failing any insight into the structure of matchings, it's exponential time'. the question is asking whether there is some known insight into the structure of BPP that makes efficient ZPP simulation possible $\endgroup$ – Sasho Nikolov Mar 28 '13 at 16:00
  • 1
    $\begingroup$ @SashoNikolov: It wasn't really meant to be a deep insight. From the wording of the question it seemed to me to be borderline for migrating to CS.SE. I decided to answer it quite literally, to wit: as far as we know, the most efficient expected running time of Las Vegas Machine that accepts a language L∈BPP is not much better than a deterministic machine which explores the possibilities brute-force. Answers which say that it might be some polynomial upper bound if some conditions hold are excellent and informative, and I vote them up for that; but I address the actual question. $\endgroup$ – Niel de Beaudrap Mar 28 '13 at 16:04
  • 1
    $\begingroup$ I think this is a nice answer (also more readable now after edit). We don't have a conditional result like "P=ZPP implies P=BPP" or "ZPP=BPP implies P=BPP" so it is still possible that we can simulate BPP by ZP algorithms faster than with deterministic algorithms. However the relativization result seems to imply that this cannot happen by any relativizing simulation, do I understand correctly? $\endgroup$ – Kaveh Mar 28 '13 at 22:42

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.