Le BPP contre P est-il un vrai problème après que nous savons que le BPP réside dans P / poly?

Nous savons (pour le moment environ 40 ans, merci Adleman, Bennet et Gill) que l'inclusion BPP P / poly, et un BPP / poly P / poly encore plus fort . Le "/ poly" signifie que nous travaillons de manière non uniforme (un circuit séparé pour chaque longueur d'entrée ), tandis que P sans ce "/ poly" signifie que nous avons une machine de Turing pour toutes les longueurs d'entrée n possibles , même plus longue que, disons, n = le nombre de secondes jusqu'au prochain "Big Bang".$\subseteq$ $\subseteq$ $n$$n$$n$

Question 1: Quelles nouveautés une preuve (ou une réfutation) de BPP = P contribuerait-elle à nos connaissances après avoir connu BPP $\subseteq$ P / poly?

Sous «nouveau», j'entends toutes les conséquences vraiment surprenantes, comme l'effondrement / la séparation d'autres classes de complexité. Comparez cela avec les conséquences de la preuve / non-preuve de NP $\subseteq$ P / poly.

[AJOUTÉ 08.10.2017]: Une conséquence vraiment surprenante de BPP $\not\subseteq$ P serait que, comme le montrent Impagliazzo et Wigderson , tous les (!) Problèmes dans E = DTIME $[2^{O(n)}]$ auraient circuits de taille $2^{o(n)}$ . Merci à Ryan d'avoir rappelé ce résultat.

Question 2: Pourquoi ne pouvons-nous pas prouver BPP = P de la même manière que la preuve de BPP / poly $\subseteq$ P / poly?

Un problème "évident" est le problème du domaine fini vs infini: les circuits booléens fonctionnent sur des domaines finis , tandis que les machines de Turing fonctionnent sur l'ensemble entier $\{0,1\}^*$ de $0$ - $1$ chaînes de n'importe quelle longueur. Ainsi, pour dérandomiser les circuits booléens probabilistes, il suffit de prendre la majorité des copies indépendantes d'un circuit probabiliste et d'appliquer l'inégalité de Chernoff, ainsi que l'union liée. Bien sûr, sur des domaines infinis , cette règle de majorité simple ne fonctionnera pas.

Mais est-ce (domaine infini) un véritable "obstacle"? En utilisant les résultats de la théorie de l'apprentissage statistique (dimension VC), nous pouvons déjà prouver que BPP / poly $\subseteq$ P / poly est également valable pour les circuits travaillant sur des domaines infinis , comme les circuits arithmétiques (travaillant sur tous les nombres réels); voir par exemple cet article de Cucker et al. Lors de l'utilisation d'une approche similaire, il suffirait de montrer que la dimension VC des machines de Turing poly-temps ne peut pas être trop grande. Quelqu'un a-t-il vu des tentatives pour franchir cette dernière étape?

Les résultats (connus sous le nom de convergence uniforme en probabilité ) impliquent alors ce qui suit: si pour chaque entrée , une fonction choisie au hasard (sous une certaine distribution de probabilité sur ) satisfait pour une constante , alors peut être calculé sur toutes les entrées comme une majorité de certains des fonctions (fixe) de . Voir, par exemple, Corollaire 2 dans l'article de Haussler . [Pour que cela tienne, il y a quelques conditions de mesurabilité douces sur ] f ∈ F F P r o b { f ( x ) = f ( x ) } ≥ 1 / 2 + c c > 0 f ( x ) x ∈ X m = O ( v ) F $x\in X$$\mathbf{f}\in F$$F$$\mathrm{Prob}\{\mathbf{f}(x)=f(x)\}\geq 1/2+c$$c>0$$f(x)$$x\in X$$m=O(v)$$F$$F$

Par exemple, si est l'ensemble de tous les polynômes calculables par des circuits arithmétiques de taille , alors tous les polynômes de ont un degré au plus . En utilisant des limites supérieures connues sur le nombre de modèles nuls de polynômes (voir, par exemple, cet article ), on peut montrer que la dimension VC de est . Cela implique l'inclusion BPP / poly P / poly pour les circuits arithmétiques.$F$$f:\mathbb{R}^n\to\mathbb{R}$$\leq s$$F$$D=2^s$$F$$O(n\log D)=O(ns)$$\subseteq$

Je ne sais pas à quel point c'est une réponse, je me livre à une rumination.

La question 1 pourrait également être posée à propos de P NP et avec une réponse similaire - les techniques / idées utilisées pour prouver le résultat seraient la grande percée plus que la conclusion elle-même.$\neq$

Pour la question 2, je veux partager quelques informations et une réflexion. Presque toutes les techniques et idées que nous avons pour BPP = P, pour autant que je sache, passent par la "dérandomisation": étant donné toute machine de Turing probabiliste de polytime, construisez un PRG pour l'alimenter en un tas de bits choisis de manière déterministe au lieu d'aléatoire ceux, de sorte que son comportement est très similaire à son comportement sur des bits vraiment aléatoires. Donc, avec des générateurs pseudo-aléatoires assez bons, nous obtenons BPP = P. (Le "monde de BPP = P" de Goldreich prouve que toute preuve de BPP = P doit être équivalente à cela.)

C'est à peu près dans la ligne de BPP P / poly, sauf que là, le PRG est la chaîne de conseil qui est produite par magie. La meilleure réponse à votre question 2 est peut-être qu'en P, nous n'avons pas de magie et devons nous-mêmes proposer la chaîne de conseils. La dérandomisation est également l'idée derrière le résultat de 2004 SL = L, en utilisant des outils tels que des graphiques d'extension.$\subseteq$

Examinons maintenant ce qu'une telle preuve impliquerait pour un seul algorithme particulier, le test de primalité de Miller-Rabin. Cela montrerait l'existence d'un générateur déterministe qui sélectionne une séquence d'entiers pour alimenter le test de primalité de Miller-Rabin de telle sorte que, si et seulement si tous les entiers réussissaient, le nombre d'origine était premier.

Si je comprends bien (bien que je ne sois pas un expert), la question de savoir si une telle liste existe et à quel point les chiffres qu’elle contient peut être (en particulier s’il suffit de vérifier tous les chiffres ci-dessous certains) semble une question théorie des nombres et est étroitement liée aux formes de démonstration de l'hypothèse de Riemann généralisée. Voir cette question . Je ne pense pas qu'il y ait une implication formelle ici, mais cela ne semble pas être quelque chose que nous nous attendons à obtenir la semaine prochaine comme corollaire miniature accidentel d'une construction PRG beaucoup plus générale.