<p>I'd imagine that you'd have to go from first principles, by taking a TM that exhibits an arbitrary BPP algorithm and simulating it in P. This is how <a href="http://en.wikipedia.org/wiki/Sipser%E2%80%93Lautemann_theorem">it is shown that</a> $\mathsf{BPP} \in \Sigma_2 \cap \Pi_2$. In particular, you have to "derandomize" the space of random choices much like it is done for specific problems, where a small set of carefully chosen seeds gives enough pseudorandomness.</p>

CC BY-SA 3.0
2013-11-26T19:11:27.470Z
2013-11-26T19:11:27.470Z
Suresh Venkat
<p>Although there aren't any problems known to be $\mathsf{BPP}$-complete (and Sipser gave an oracle relative to which $\mathsf{BPP}$ doesn't have complete problems), one topic to look at here is pseudorandom generators. The existence of a good enough pseudorandom generator implies $\mathsf{BPP} = \mathsf{P}$. This isn't $\mathsf{BPP}$-complete, but it does have the feature that a single algorithm could show $\mathsf{BPP}=\mathsf{P}$.</p>

<p>Also, although not $\mathsf{BPP}$-complete, Polynomial Identity Testing is a good single problem in $\mathsf{BPP}$ to focus on derandomizing. Many problems in $\mathsf{BPP}$ are actually in $\mathsf{RP}$ or $\mathsf{coRP}$, often due to the Schwarz-Zippel Lemma (in fact, there are apparently very few known candidates that are known to be in $\mathsf{BPP}$ but not in $\mathsf{RP} \cup \mathsf{coRP}$, see <a href="https://cstheory.stackexchange.com/questions/11425/problem-in-bpp-but-not-known-to-be-in-rp-or-co-rp">this related question</a>), so derandomizing PIT would derandomize a whole bunch of problems. Furthermore, derandomizing PIT is known to imply strong lower bounds on $\mathsf{NEXP}$.</p>

CC BY-SA 3.0
2013-11-26T20:43:41.053Z
But having good enough PRGs separates the harder $P$ and $NP$ and may be infeasible before the truth of $P=BPP$ itself is known. So there is no one problem that is milder than what you are suggesting.... correct?
Turbo
CC BY-SA 3.0
2013-11-26T22:17:55.603Z
As far as I know, good enough PRGs are not known to imply $P \neq NP$. Showing $P = BPP$ is known to imply lower bounds on NEXP (Kabanets-Impagliazzo), so showing at least some lower bound like this is necessary no matter what approach you use to try to show P=BPP.
Joshua Grochow
CC BY-SA 3.0
2013-11-26T22:36:21.800Z
OK Thankyou for the update. I think I was confusing with cryptosecure PRGs.
Turbo
CC BY-SA 3.0
2013-11-26T22:45:13.607Z
http://en.wikipedia.org/wiki/Pseudorandom_generator#Cryptography
Turbo
CC BY-SA 3.0
2013-11-26T20:22:00.490Z
2013-11-26T20:22:00.490Z
2017-04-13T12:32:28.117Z
Joshua Grochow
<p>Typically to show $P=NP$, one has to show an NP complete problem has a polynomial time solution and to show $P\neq NP$, has to show an NP complete problem has superpolynomial lower bound. These are broadly the general techniques.</p>

<p>For showing $P=BPP$ or $P\neq BPP$ what strategies can be used or used? It is not like there is one problem in BPP that can either be shown to be derandomized or not be derandomized that solves the question.</p>

CC BY-SA 3.0
2013-11-26T17:40:28.973Z
There are at least four questions in your super-question. It might help to separate them out.
Suresh Venkat
CC BY-SA 3.0
2013-11-26T17:50:24.383Z
@SureshVenkat done!!
Turbo
CC BY-SA 3.0
2013-11-26T19:20:47.077Z
I think Eric Allender is the expert on the topic. See his presentation [Circuit Complexity meets the Theory of Randomness](http://www.cs.rutgers.edu/~allender/buffalo.ppt). IIRC, Eric has a strategy for showing P=BPP using Kolmogorov complexity. You may want to check his recent papers:
Kaveh
CC BY-SA 3.0
2013-11-26T19:30:24.287Z
[Limits on the Computational Power of Random Strings](http://ftp.cs.rutgers.edu/pub/allender/limitsk.pdf), [Reductions to the set of random strings: The resource-bounded case](http://ftp.cs.rutgers.edu/pub/allender/ttrt.pdf), [Curiouser and Curiouser: The Link between Incompressibility and Complexity](http://ftp.cs.rutgers.edu/pub/allender/curiouser.pdf), [Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic](http://ftp.cs.rutgers.edu/pub/allender/PA.pdf).
Kaveh
CC BY-SA 3.0
2013-11-26T20:54:23.430Z
@Kaveh could you elaborate your answer?
Turbo
CC BY-SA 3.0
2013-11-26T21:35:04.007Z
I can elaborate a bit but I would prefer if someone more knowledgeable (or ideally [Eric Allender](http://cstheory.stackexchange.com/users/17282/eric-allender) himself) writes an answer.
Kaveh
<cc.complexity-theory><complexity-classes><randomness><proofs>
Proof Strategies on P versus BPP
Turbo
# Proof Strategies on P versus BPP

(Asked by: username_0 on 2013-11-26)

Typically to show $P=NP$, one has to show an NP complete problem has a polynomial time solution and to show $P\neq NP$, has to show an NP complete problem has superpolynomial lower bound. These are broadly the general techniques.

For showing $P=BPP$ or $P\neq BPP$ what strategies can be used or used? It is not like there is one problem in BPP that can either be shown to be derandomized or not be derandomized that solves the question.

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

> **Comments:**
> **username_1**: There are at least four questions in your super-question. It might help to separate them out.  
> **username_0**: @SureshVenkat done!!  
> **username_2**: I think Eric Allender is the expert on the topic. See his presentation [Circuit Complexity meets the Theory of Randomness](http://www.cs.rutgers.edu/~allender/buffalo.ppt). IIRC, Eric has a strategy for showing P=BPP using Kolmogorov complexity. You may want to check his recent papers:  
> **username_2**: [Limits on the Computational Power of Random Strings](http://ftp.cs.rutgers.edu/pub/allender/limitsk.pdf), [Reductions to the set of random strings: The resource-bounded case](http://ftp.cs.rutgers.edu/pub/allender/ttrt.pdf), [Curiouser and Curiouser: The Link between Incompressibility and Complexity](http://ftp.cs.rutgers.edu/pub/allender/curiouser.pdf), [Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic](http://ftp.cs.rutgers.edu/pub/allender/PA.pdf).  
> **username_0**: @username_2 could you elaborate your answer?  
> **username_2**: I can elaborate a bit but I would prefer if someone more knowledgeable (or ideally [Eric Allender](http://cstheory.stackexchange.com/users/17282/eric-allender) himself) writes an answer.  

---

## 2 answers

### Answer by username_3 on 2013-11-26. Score: 9 | Accepted answer

Although there aren't any problems known to be $\mathsf{BPP}$-complete (and Sipser gave an oracle relative to which $\mathsf{BPP}$ doesn't have complete problems), one topic to look at here is pseudorandom generators. The existence of a good enough pseudorandom generator implies $\mathsf{BPP} = \mathsf{P}$. This isn't $\mathsf{BPP}$-complete, but it does have the feature that a single algorithm could show $\mathsf{BPP}=\mathsf{P}$.

Also, although not $\mathsf{BPP}$-complete, Polynomial Identity Testing is a good single problem in $\mathsf{BPP}$ to focus on derandomizing. Many problems in $\mathsf{BPP}$ are actually in $\mathsf{RP}$ or $\mathsf{coRP}$, often due to the Schwarz-Zippel Lemma (in fact, there are apparently very few known candidates that are known to be in $\mathsf{BPP}$ but not in $\mathsf{RP} \cup \mathsf{coRP}$, see [this related question](https://cstheory.stackexchange.com/questions/11425/problem-in-bpp-but-not-known-to-be-in-rp-or-co-rp)), so derandomizing PIT would derandomize a whole bunch of problems. Furthermore, derandomizing PIT is known to imply strong lower bounds on $\mathsf{NEXP}$.

> **Comments:**
> **username_0**: But having good enough PRGs separates the harder $P$ and $NP$ and may be infeasible before the truth of $P=BPP$ itself is known. So there is no one problem that is milder than what you are suggesting.... correct?  
> **username_3**: As far as I know, good enough PRGs are not known to imply $P \neq NP$. Showing $P = BPP$ is known to imply lower bounds on NEXP (Kabanets-Impagliazzo), so showing at least some lower bound like this is necessary no matter what approach you use to try to show P=BPP.  
> **username_0**: OK Thankyou for the update. I think I was confusing with cryptosecure PRGs.  
> **username_0**: http://en.wikipedia.org/wiki/Pseudorandom_generator#Cryptography  

---

### Answer by username_1 on 2013-11-26. Score: 6

I'd imagine that you'd have to go from first principles, by taking a TM that exhibits an arbitrary BPP algorithm and simulating it in P. This is how [it is shown that](http://en.wikipedia.org/wiki/Sipser%E2%80%93Lautemann_theorem) $\mathsf{BPP} \in \Sigma\_2 \cap \Pi\_2$. In particular, you have to "derandomize" the space of random choices much like it is done for specific problems, where a small set of carefully chosen seeds gives enough pseudorandomness.


---

