8
$\begingroup$

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.

$\endgroup$
6

2 Answers 2

9
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Turbo
    Commented Nov 26, 2013 at 20:43
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Nov 26, 2013 at 22:17
  • $\begingroup$ OK Thankyou for the update. I think I was confusing with cryptosecure PRGs. $\endgroup$
    – Turbo
    Commented Nov 26, 2013 at 22:36
  • $\begingroup$ en.wikipedia.org/wiki/Pseudorandom_generator#Cryptography $\endgroup$
    – Turbo
    Commented Nov 26, 2013 at 22:45
6
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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