- cc.complexity-theory circuit-complexity machine-learning derandomization
- Updated Fri, 27 May 2022 10:05:07 GMT

We know (for now about 40 years, thank Adleman, Bennet and Gill) that the inclusion **BPP** $\subseteq$ **P**/poly, and an even stronger **BPP**/poly $\subseteq$ **P**/poly hold.
The "/poly" means that we work non-uniformly (a separate circuit for each input length $n$), while **P** without this "/poly" means we have *one* Turing machine for *all* possible input lengths $n$, even longer than, say, $n$ = the number of seconds to the next "Big Bang".

Question 1:What new would a proof (or disproof) ofBPP=Pcontribute to our knowledge after we knowBPP$\subseteq$P/poly?

Under "new" I mean any really surprising consequences, like collapse/separation of other complexity classes. Compare this with consequences the
proof/disproof of **NP** $\subseteq$ **P**/poly would deliver.

[ADDED 08.10.2017]: One really surprising consequence
of **BPP** $\not\subseteq$ **P** would be that, as shown by Impagliazzo and Wigderson, *all*(!) problems in
**E** = DTIME$[2^{O(n)}]$ would have circuits of size $2^{o(n)}$.
Thanks to Ryan for recalling this result.

Question 2:Why we cannot proveBPP=Palong similar lines as the proof ofBPP/poly $\subseteq$P/poly?

One "obvious" obstacle is finite vs. infinite domain issue: boolean circuits work over *finite* domains, whereas Turing machines
work over entire set $\{0,1\}^*$ of $0$-$1$ strings of any length. So, to derandomize probabilistic boolean circuits, it
is enough to take the majority of independent copies of a probabilistic circuit, and to apply Chernoff's inequality, together with the union bound. Of course, over *infinite* domains, this simple majority rule won't work.

But is this (infinite domain) a real "obstacle"?
By using results from statistical learning theory (VC dimension), we already *can* prove that **BPP**/poly $\subseteq$ **P**/poly
holds also for circuits working over *infinite* domains, like arithmetic circuits (working over all real numbers); see e.g. this paper of Cucker at al.
When using a similar approach, all we would need is to show that the VC dimension of poly-time Turing machines cannot be too large. Has anybody seen any attempts to make this latter step?

The results (known as uniform convergence in probability)
then imply the following: if for each input $x\in X$, a randomly picked function $\mathbf{f}\in F$ (under some probability distribution on $F$)
satisfies $\mathrm{Prob}\{\mathbf{f}(x)=f(x)\}\geq 1/2+c$
for a constant $c>0$,
then $f(x)$ can be computed on *all* inputs $x\in X$ as a majority of some $m=O(v)$ (fixed) functions from $F$. See, e.g. Corollary 2 in Haussler's paper.
[For this to hold, there are some mild measurability conditions on $F$.]

For example, if $F$ is the set of all polynomials $f:\mathbb{R}^n\to\mathbb{R}$ computable by arithmetic circuits of size $\leq s$, then all polynomials in $F$ have degree at most $D=2^s$.
By using known upper bounds on the number of zero-patterns of polynomials (see, e.g. this paper),
one can show that the VC dimension of $F$ is $O(n\log D)=O(ns)$. This implies the inclusion **BPP**/poly $\subseteq$ **P**/poly for
arithmetic circuits.

Not sure how much of an answer this is, I'm just indulging in some rumination.

Question 1 could be equally asked about P $\neq$ NP and with a similar answer -- the techniques/ideas used to prove the result would be the big breakthrough more so than the conclusion itself.

For Question 2 I want to share some background and a thought. Pretty much all the techniques and ideas we have for BPP=P, as far as I'm aware, go via "derandomization": Given any probabilistic polytime Turing Machine, construct a PRG to feed it a bunch of deterministically chosen bits instead of random ones, such that its behavior is very similar to its behavior on truly random bits. So with good enough pseudorandom generators, we get BPP=P. (Goldreich's "World of BPP=P" gives evidence that any proof of BPP=P must equate to this.)

This is pretty much along the lines of BPP $\subseteq$ P/poly, except there, the PRG is the advice string which is produced by magic. Perhaps the best answer to your Question 2 is that in P we have no magic and must come up with the advice string ourselves. Derandomization is also the idea behind the 2004 result SL=L, using tools like expander graphs.

Now consider what such a proof would imply for just one particular algorithm, the Miller-Rabin primality test. It would show the existence of some deterministic generator that picks out a sequence of integers to feed to the Miller-Rabin primality test such that, if and only if all the integers passed, then the original number was prime.

As I understand it (though I am no expert), the question of whether such a list exists and how small the numbers in it can be (in particular if it sufficices to check all the numbers below some bound) seems quite a deep question in number theory and is closely related to proving forms of the generalized Riemann Hypothesis. See this question. I don't think there's a formal implication here, but it doesn't seem like something we expect to get next week as an accidental miniature corollary of a much more general PRG construction.

- +0 – Interesting thoughts! Oded's paper suggests that Q2 indeed reduces to "existence vs. construction" of PRGs. In derandomization via VC dimension, algorithmic aspects are entirely ignored. — Oct 07, 2017 at 15:12
- +2 – Thanks to all (Kaveh, Ricky, Ryan, Sasho and "usul"): I've learned a lot from your comments. "Uniformity" was
*never*an issue in my life, hence the naivity of my questions. I am accepting the answer of "usul". Complemented by very interesting remarks of Kaveh, Ricky, Ryan and Sasho, this answers my both questions. — Oct 09, 2017 at 19:13

External links referenced by this document:

- https://en.wikipedia.org/wiki/P/poly
- https://en.wikipedia.org/wiki/Uniform_convergence_in_probability
- https://mathoverflow.net/questions/165809/how-strong-is-this-conjecture-z-nz-is-generated-by-small-elements
- http://www.ams.org/journals/jams/2001-14-03/S0894-0347-01-00367-8/
- http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf
- http://www.sciencedirect.com/science/article/pii/089054019290010D
- http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/random-circuits.pdf