22
$\begingroup$

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) of BPP = P contribute to our knowledge after we know BPP $\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 prove BPP = P along similar lines as the proof of BPP/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?


NOTE [added 07.10.2017]: In the context of derandomization, the VC dimension of a class $F$ of functions $f:X\to Y$ is defined as the maximum number $v$ for which there are functions $f_1,\ldots,f_v$ in $F$ such that for every $S\subseteq\{1,\ldots,v\}$ there is a point $(x,y)\in X\times Y$ with $f_i(x)=y$ iff $i\in S$. I.e. we shatter not the sets of points via functions but rather sets of functions via points. (The two resulting definitions of the VC dimension are related, but exponentially.)

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.

$\endgroup$
15
  • 3
    $\begingroup$ Regarding Q1: a disproof would show surprisingly small circuits for every problem solvable in 2^(O(n)) time, by Impagliazzo-Wigderson (as you probably know?) $\endgroup$ Oct 6, 2017 at 22:28
  • 1
    $\begingroup$ I am confused by Q2. It seems obvious that the VC dimension of a poly-time TM is infinite. I.e. for any finite set $X \subseteq \{0,1\}^*$ and any $S \subseteq X$ there exists a polytime TM that accepts the elements of $S$ and rejects the elements of $X \setminus S$. The key thing is that $X$ is finite, so the polytime restriction is basically irrelevant. $\endgroup$ Oct 7, 2017 at 6:02
  • 1
    $\begingroup$ Re Q2, the inclusion doesn't really have much to do with complexity class and computational power I think, it is about the amount of random bits versus the amount of advice, so I don't think it gives us any information about the nature of efficient computation. $\endgroup$
    – Kaveh
    Oct 7, 2017 at 15:24
  • 1
    $\begingroup$ @Kaveh: the hint "amount of random bits vs. the amount of advice" is worth to think on! But in my (layman's) mind, even in questions like P vs. NP, we do not actually care about an "explicit" construction of a (uniform) TM. Such questions only ask about the existence of efficient algorithms. Of course, a construction is a "no doubts" proof of the existence. But there can be some less direct proofs as well. So, the things reduce to extending "existence for each $n$" to showing "existence for all $n$". That is, $\forall\exists$ to $\exists\forall$. $\endgroup$
    – Stasys
    Oct 7, 2017 at 15:53
  • 1
    $\begingroup$ Even if you fix the running time, the VC-dim will be infinite. What you can hope to do is to bound the VC-dim of time $T$ bounded TMs running on input size $n$. But if you think about the argument then, you would have to take a majority of potentially different TMs for every $n$: nonuniformity. $\endgroup$ Oct 8, 2017 at 20:42

1 Answer 1

20
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Stasys
    Oct 7, 2017 at 15:12
  • 2
    $\begingroup$ 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. $\endgroup$
    – Stasys
    Oct 9, 2017 at 19:13

Your Answer

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

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