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

16

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". nnnn

Question 1: Quelles nouveautés une preuve (ou une réfutation) de BPP = P contribuerait-elle à nos connaissances après avoir connu BPP 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 P / poly.

[AJOUTÉ 08.10.2017]: Une conséquence vraiment surprenante de BPP P serait que, comme le montrent Impagliazzo et Wigderson , tous les (!) Problèmes dans E = DTIME [2O(n)] auraient circuits de taille 2o(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 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 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?


NOTE [ajouté le 07.10.2017]: Dans le contexte de la dérandomisation, la dimension VC d'une classe F de fonctions F:XOui est définie comme le nombre maximal v pour lequel il existe des fonctions F1,,Fv dans F telles que , pour chaque S{1,,v} il y a un point (X,y)X×Oui avec Fje(X)=y ssi jeS . C'est-à-dire que nous ne brisons pas les ensembles de points via les fonctions mais plutôt les ensembles de fonctions via les points. (Les deux définitions résultantes de la dimension VC sont liées, mais de façon exponentielle.)

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 ] fF F P r o b { f ( x ) = f ( x ) } 1 / 2 + c c > 0 f ( x ) x X m = O ( v ) F FXXFFFProb{F(X)=F(X)}1/2+cc>0F(X)XXm=O(v)FF

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.Ff:RnRsFD=2sFO(nlogD)=O(ns)

Stasys
la source
3
Concernant Q1: un disproof montrerait des circuits étonnamment petits pour chaque problème résolu en 2 ^ (O (n)) temps, par Impagliazzo-Wigderson (comme vous le savez probablement?)
Ryan Williams
1
Je suis confus par Q2. Il semble évident que la dimension VC d'un poly-temps TM est infinie. À- dire pour tout ensemble fini et tout il existe une TM polynomial qui accepte les éléments de et rejette les éléments de . L'essentiel est que est fini, donc la restriction de polytemps n'est fondamentalement pas pertinente. X{0,1}SXSXSX
Sasho Nikolov
1
Concernant Q2, l'inclusion n'a pas vraiment grand-chose à voir avec la classe de complexité et la puissance de calcul, je pense, il s'agit de la quantité de bits aléatoires par rapport à la quantité de conseils, donc je ne pense pas que cela nous donne des informations sur la nature de calcul efficace.
Kaveh
1
@Kaveh: l'indice "quantité de bits aléatoires par rapport à la quantité de conseils" mérite réflexion! Mais dans mon esprit (profane), même dans des questions comme P vs NP, nous ne nous soucions pas réellement d'une construction "explicite" d'une MT (uniforme). Ces questions ne portent que sur l' existence d'algorithmes efficaces. Bien sûr, une construction est une preuve "sans aucun doute" de l'existence. Mais il peut aussi y avoir des preuves moins directes . Ainsi, les choses se réduisent à étendre "l'existence pour chaque " à montrer "l'existence pour tout ". C'est-à-dire que pour . nn
Stasys
1
Même si vous fixez la durée de fonctionnement, le VC-dim sera infini. Ce que vous pouvez espérer faire, c'est de limiter la VC-dim des bornées dans le temps fonctionnant sur la taille d'entrée . Mais si vous réfléchissez à l'argument, vous devrez prendre une majorité de MT potentiellement différentes pour chaque : non-uniformité. Tnn
Sasho Nikolov

Réponses:

17

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.

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.

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.

usul
la source
Pensées intéressantes! L'article d'Oded suggère que le T2 se réduit en effet à «l'existence contre la construction» des PRG. Dans la dérandomisation via la dimension VC, les aspects algorithmiques sont entièrement ignorés.
Stasys
2
Merci à tous (Kaveh, Ricky, Ryan, Sasho et "usul"): J'ai beaucoup appris de vos commentaires. "L'uniformité" n'a jamais été un problème dans ma vie, d'où la naïveté de mes questions. J'accepte la réponse de "usul". Complété par des remarques très intéressantes de Kaveh, Ricky, Ryan et Sasho, cela répond à mes deux questions.
Stasys