# Proof Strategies on P versus BPP

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.

• There are at least four questions in your super-question. It might help to separate them out. – Suresh Venkat Nov 26 '13 at 17:40
• @SureshVenkat done!! – Turbo Nov 26 '13 at 17:50
• I think Eric Allender is the expert on the topic. See his presentation Circuit Complexity meets the Theory of Randomness. IIRC, Eric has a strategy for showing P=BPP using Kolmogorov complexity. You may want to check his recent papers: – Kaveh Nov 26 '13 at 19:20
• @Kaveh could you elaborate your answer? – Turbo Nov 26 '13 at 20:54

## 2 Answers

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), so derandomizing PIT would derandomize a whole bunch of problems. Furthermore, derandomizing PIT is known to imply strong lower bounds on $\mathsf{NEXP}$.

• 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 Nov 26 '13 at 20:43
• 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 Nov 26 '13 at 22:17
• OK Thankyou for the update. I think I was confusing with cryptosecure PRGs. – Turbo Nov 26 '13 at 22:36
• en.wikipedia.org/wiki/Pseudorandom_generator#Cryptography – Turbo Nov 26 '13 at 22:45

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