<p>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.</p>

<p>Next, consider the class <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aP#promisebpp" rel="nofollow">$\mathsf{PromiseBPP}$</a>, for which the following problem is "$\mathsf{PromiseBPP}$-hard":</p>

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

<p>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.</p>

<p>Notice that even proving $\mathsf{RP} \subseteq \mathsf{ZPTIME}[2^{n^{\varepsilon}}]$ is also open, and proving <em>that</em> 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 &gt; 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: </p>

<ol>
<li><p>There is a $c$ such that for all $\varepsilon &gt; 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. </p></li>
<li><p>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.</p></li>
</ol>

CC BY-SA 3.0
2013-04-01T20:00:25.457Z
Thanks to Niel for taking the time to make my response legible :)
Ryan Williams
CC BY-SA 3.0
2013-04-01T22:49:53.753Z
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))?
Sasho Nikolov
CC BY-SA 3.0
2013-04-02T17:14:13.473Z
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.
Ryan Williams
CC BY-SA 3.0
2013-04-03T05:24:12.947Z
Ryan: If I wanted to understand your paper what book/papers on circuit complexity do you recommend to be familiar with?
Turbo
CC BY-SA 3.0
2013-04-04T21:26:04.463Z
Hi Arul, luckily Bill Gasarch asked me this question a while back, and put up the following webpage of links: http://www.cs.umd.edu/~gasarch/ryan/ryan.html
Ryan Williams
CC BY-SA 3.0
2013-04-01T01:40:33.843Z
2013-04-02T23:53:52.987Z
2013-04-02T23:53:52.987Z
Ryan Williams
<p>It depends on what assumptions you are willing to make.</p>

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

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

CC BY-SA 3.0
2013-03-28T03:42:36.020Z
2013-03-28T03:42:36.020Z
Or Meir
<p>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.</p>

<p>For a <strong>BPP</strong> 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.</p>

<p>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$.</p>

<p>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 <em>deterministically</em> tested all possible random strings. We get no asymptotic advantage in simulating <strong>BPP</strong> algorithms randomly in a zero-error setting, beyond what we can do deterministically by brute-force.</p>

<p>Note that this same argument gives rise to an oracle separation between <strong>BPP</strong> and <strong>ZPP</strong>, <em>i.e.</em>&nbsp;there is an oracle $A$ such that $$\mathsf{ZPP}^A \subsetneqq \mathsf{BPP}^A$$
because the <strong>ZPP</strong> algorithm takes exponential time, while a <strong>BPP</strong> 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.</p>

CC BY-SA 3.0
2013-03-28T15:32:07.267Z
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
Sasho Nikolov
CC BY-SA 3.0
2013-03-28T15:47:16.693Z
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?
Niel de Beaudrap
CC BY-SA 3.0
2013-03-28T16:00:10.813Z
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
Sasho Nikolov
CC BY-SA 3.0
2013-03-28T16:04:11.193Z
@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.
Niel de Beaudrap
CC BY-SA 3.0
2013-03-28T16:10:25.487Z
"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" is that true? because your answer just says that a naive approach works just as well with or without randomness
Sasho Nikolov
CC BY-SA 3.0
2013-03-28T16:22:57.653Z
@SashoNikolov: Is your concern that I'm claiming that there is no better zero-error method than essentially the naive approach, in order to tell (with zero error) whether the bounded-error algorithm has a bias towards YES rather than NO? Do I make it sound as if there will *never* be such an approach, as opposed to there being no approach *with our current state of information*, where we're forced to treat the BPP algorithm as a black box? Or do you think that, as I've written the answer, it is wrong for some other reason?
Niel de Beaudrap
CC BY-SA 3.0
2013-03-28T16:27:32.593Z
sorry for not being clear: yes, my concern is that it comes off as if you are saying that the naive approach has to be best possible. also, even though i trust you that we don't know anything better unconditionally, maybe there is some evidence/reference to support that claim?
Sasho Nikolov
CC BY-SA 3.0
2013-03-28T17:21:49.970Z
@SashoNikolov: I have tried now to clarify my argument to make it explicit that I'm making an argument about oracles. I've added some remarks to the end about an oracle separation between **ZPP** and **BPP** which is germane to the discussion that we have been having.
Niel de Beaudrap
CC BY-SA 3.0
2013-03-28T22:42:00.230Z
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?
Kaveh
CC BY-SA 3.0
2013-03-27T18:41:07.113Z
2013-03-28T17:18:17.250Z
2013-03-28T17:18:17.250Z
Niel de Beaudrap
<p><a href="http://en.wikipedia.org/wiki/BPP_%28complexity%29">$\mathsf{BPP}$</a> and <a href="http://en.wikipedia.org/wiki/ZPP_%28complexity%29">$\mathsf{ZPP}$</a> are two of basic probabilistic complexity classes.</p>

<p>$\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).</p>

<p>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.</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Las_Vegas_algorithm">Las Vegas algorithms</a> and $\mathsf{ZPP} = \mathsf{ZPTime}(n^{O(1)})$.</p>

<p>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?</p>

<p>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&gt;0$?</p>

CC BY-SA 3.0
2013-03-27T15:11:24.900Z
What is n, the length of the input? Why can we accept in $2^n$?
domotorp
CC BY-SA 3.0
2013-03-28T12:17:50.560Z
$2^{\mathrm{poly}(n)-n^\epsilon}$ is the same thing as $2^{\mathrm{poly}(n)}$.
Emil Jeřábek
CC BY-SA 3.0
2013-03-28T22:47:40.397Z
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.
Kaveh
CC BY-SA 3.0
2013-03-28T22:52:11.760Z
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.
Kaveh
<cc.complexity-theory><complexity-classes><randomness><randomized-algorithms>
What is the fastest known simulation of BPP using Las Vegas algorithms?
echuly
# What is the fastest known simulation of BPP using Las Vegas algorithms?

(Asked by: username_0 on 2013-03-27)

[$\mathsf{BPP}$](http://en.wikipedia.org/wiki/BPP_%28complexity%29) and [$\mathsf{ZPP}$](http://en.wikipedia.org/wiki/ZPP_%28complexity%29) 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](http://en.wikipedia.org/wiki/Las_Vegas_algorithm) 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$?

**Tags:** cc.complexity-theory, complexity-classes, randomness, randomized-algorithms
> **Comments:**
> **username_1**: What is n, the length of the input? Why can we accept in $2^n$?  
> **username_2**: $2^{\mathrm{poly}(n)-n^\epsilon}$ is the same thing as $2^{\mathrm{poly}(n)}$.  
> **username_3**: 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.  
> **username_3**: 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.  

---

## 3 answers

### Answer by username_4 on 2013-04-01. Score: 13

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}$](https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aP#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.

> **Comments:**
> **username_4**: Thanks to Niel for taking the time to make my response legible :)  
> **username_5**: 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))?  
> **username_4**: 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.  
> **username_6**: Ryan: If I wanted to understand your paper what book/papers on circuit complexity do you recommend to be familiar with?  
> **username_4**: Hi Arul, luckily Bill Gasarch asked me this question a while back, and put up the following webpage of links: http://www.cs.umd.edu/~gasarch/ryan/ryan.html  

---

### Answer by username_7 on 2013-03-28. Score: 8

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


---

### Answer by username_8 on 2013-03-27. Score: 4

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.

> **Comments:**
> **username_5**: 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  
> **username_8**: 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?  
> **username_5**: 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  
> **username_8**: @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.  
> **username_5**: "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" is that true? because your answer just says that a naive approach works just as well with or without randomness  
> **username_8**: @SashoNikolov: Is your concern that I'm claiming that there is no better zero-error method than essentially the naive approach, in order to tell (with zero error) whether the bounded-error algorithm has a bias towards YES rather than NO? Do I make it sound as if there will *never* be such an approach, as opposed to there being no approach *with our current state of information*, where we're forced to treat the BPP algorithm as a black box? Or do you think that, as I've written the answer, it is wrong for some other reason?  
> **username_5**: sorry for not being clear: yes, my concern is that it comes off as if you are saying that the naive approach has to be best possible. also, even though i trust you that we don't know anything better unconditionally, maybe there is some evidence/reference to support that claim?  
> **username_8**: @SashoNikolov: I have tried now to clarify my argument to make it explicit that I'm making an argument about oracles. I've added some remarks to the end about an oracle separation between **ZPP** and **BPP** which is germane to the discussion that we have been having.  
> **username_3**: 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?  

---

