Pourquoi le hasard a-t-il un effet plus fort sur les réductions que sur les algorithmes?

On suppose que le caractère aléatoire n’étend pas la puissance des algorithmes de temps polynomiaux, c’est-à-dire que est supposé tenir. D'autre part, le hasard semble avoir un effet assez différent sur les réductions de temps polynomiales . Selon le résultat bien connu de Valiant et Vazirani, la réduit à via une réduction polynomiale aléatoire. Il est peu probable que la réduction puisse être dérandonnée, car elle donnerait , ce qui est considéré comme improbable. S A T U S A T N P = U ${\bf P}={\bf BPP}$$SAT$$USAT$${\bf NP}={\bf UP}$

Je me demande quelle peut être la raison de cette situation asymétrique: une dérandomisation semble tout à fait possible dans les algorithmes probabilistes à temps polynomiaux, mais pas dans les réductions probabilistes dans le temps polynomial?

Permettez-moi d'abord de commenter le cas particulier de la réduction Valiant-Vazirani; J'espère que cela aidera à clarifier la situation générale.

La réduction Valiant-Vazirani peut être visualisée / définie de plusieurs manières. Cette réduction consiste à "essayer" de mapper une formule booléenne satisfiable à un uniquement satisfaisable , et un insatisfiable à un insatisfiable . Toutes les formules en sortie sont toujours obtenues en restreignant davantage , de sorte que l'insatisfiabilité est toujours préservée. La réduction peut être définie soit comme sortie d'un seul , soit comme sortie d'une liste de . Dans ce dernier cas, "succès" dans le cas où est défini comme ayant au moins un uniquement satisfaisableF ' F F ' F F ' F ' 1 , … , F ' t F ∈ S A T F ' $F$$F'$$F$$F'$$F$$F'$$F'_1, \ldots, F'_t$$F \in SAT$$F'_i$dans la liste. Appelez ces deux variantes "réduction de singleton" et "réduction de liste" (ceci n'est pas une terminologie standard).

Le premier point important à noter est que la probabilité de succès de la réduction de singleton est assez faible, à savoir où est le nombre de variables. Les difficultés pour améliorer cette probabilité de succès sont explorées dans le document$\Theta(1/n)$$n$

"La probabilité d'isolement de Valiant-Vazirani est-elle improbable?" par Dell et al.

http://eccc.hpi-web.de/report/2011/151/#revision1

Dans la réduction de liste, la probabilité de succès peut être grande, exemple, avec une liste de taille poly . (On peut simplement répéter la réduction de singleton plusieurs fois, par exemple.) ( n $1 - 2^{-n}$$(n)$

Or, il n’est pas du tout évident ni intuitif que nous devrions pouvoir directement dérandonner une réduction qui n’a que la probabilité de succès . En effet, aucun des résultats dureté / aléa ne donne d'hypothèses permettant de le faire dans ce cas. Il est beaucoup plus plausible que la réduction de liste puisse être dérandomisée (avec une liste un peu plus longue). Notez cependant que cela n’impliquerait pas : notre liste de formules en sortie peut contenir de nombreuses formules uniquement satisfaisables, et peut-être même plusieurs affectations satisfaisantes, et il semble sans espoir de tenter de définir un calcul acceptant uniquement sur une telle liste. N P = U $1/n$$NP = UP$

Même si nous pouvions en quelque sorte donner une réduction de liste dans laquelle un satisfiable a toujours induit une liste où la plupart des sont uniquement satisfaisables, il n’existe aucun moyen clair de le transformer. dans une réduction singleton déterministe pour l'isolement. La vraie difficulté sous-jacente est que nous ne connaissons aucune "opération à majorité approximative pour des formules uniquement satisfaisables", c’est-à-dire une réduction dont le résultat est uniquement satisfaisable si sont uniquement satisfaisables, et insatisfiables si la plupart desF ' 1 , ... , F ' t F ' j R ( F ' 1 , ... , F ' t ) F ' j F ' $F$$F'_1, \ldots, F'_t$$F'_j$$R(F'_1, \ldots, F'_t)$$F'_j$$F'_j$sont insatisfiables. Cela semble aussi être un phénomène général: les réductions produisent des objets plus complexes que des algorithmes de décision, et les propriétés de ces objets sont plus difficiles à vérifier. Il est donc difficile de combiner plusieurs de ces objets en un seul objet qui hérite d'une propriété de la majorité.

Dans le cas de Valiant-Vazirani, il ne semble même pas probable que des hypothèses de dérandonnage plausibles nous permettent d’obtenir , c’est-à-dire de réduire de manière déterministe les formules satisfaisables à des formules satisfaisables avec des solutions poly . Intuitivement, cela provient du fait que la procédure d’isolement n’a aucune idée de la taille approximative de l’ensemble de solutions de la formule donnée.≤ ( n ) $NP = FewP$$\leq$$(n)$$F$

Dans le monde oracle, il est facile de donner des exemples où le hasard nous donne beaucoup plus de pouvoir. Considérons, par exemple, le problème de la détermination du zéro d'une fonction booléenne équilibrée. Un algorithme randomisé accomplit cela en utilisant des requêtes avec une probabilité de succès constante, alors que tout algorithme déterministe nécessite au moins requêtes.n /$O(1)$$n/2$

Voici une autre situation dans laquelle on pense que la randomisation peut aider. Supposons que nous voulions maximiser une fonction sous-modulaire monotone sur une contrainte matroïde. Il existe deux algorithmes différents qui donnent une approximation de , ce qui est optimal dans ce modèle par le résultat de Vondrák. Les deux algorithmes doivent calculer une fonction de la forme , où est une distribution avec un support exponentiel. Le calcul exact de cette fonction est trop coûteux, mais l’échantillonnage permet d’en approcher le résultat et donne un algorithme aléatoire. En revanche, l'algorithme déterministe le plus connu, l'algorithme glouton, donne une approximation .E x ~ X f ( x ) X 1 /$1-1/e$$\mathbb{E}_{x \sim X} f(x)$$X$$1/2$

Une situation similaire se produit dans la maximisation sous-modulaire non contrainte (ici, la fonction n'est pas nécessairement monotone). L'algorithme révolutionnaire donne une récente optimale approximation, mais sa version déterministe donne seulement 1 / 3 approximation. Ici, la randomisation se manifeste soit de la même manière que dans le cas monotone, soit (dans une version différente de l’algorithme) en effectuant quelques choix aléatoires en cours de route.$1/2$$1/3$

L' un des auteurs de ces derniers en papier que conjectures est le meilleur qu'un algorithme déterministe peut réaliser, et nous pouvons de la même conjecture que $1/3$ est le meilleur qui peut être atteint dans le problème précédent. Si ces hypothèses sont vraies, alors il s'agit d'une situation très naturelle dans laquelle la randomisation est une aide précieuse.$1/2$

Récemment, Dobzinski et Vondrák ont ​​montré comment transformer les limites inférieures de la valeur oracle (pour les algorithmes aléatoires) en résultats de dureté, conditionnés par un NP différent de RP (l'ingrédient clé est le décodage de liste). Il convient de mentionner que la transformation repose sur la méthode spécifique utilisée pour prouver les limites inférieures d’Oracle. Peut-être est-il vrai que les limites inférieures de l'oracle de la valeur déterministe se traduisent également en résultats de dureté.

Une des raisons pour lesquelles il peut sembler étrange pour vous de penser que les réductions randomisées de à U P sont plus apparentes (ou supposées) que les comparaisons de B P P à P , est parce que vous êtes peut-être tenté de penser le hasard comme quelque chose de puissant (ou pas puissant) indépendamment de la "machine" à laquelle vous l'ajoutez (si nous caricaturons ces classes de complexité en tant que classes issues de modèles de machine).$\mathsf{NP}$$\mathsf{UP}$$\mathsf{BPP}$$\mathsf P$

Et pourtant, ces réductions de puissance différentes existent. En fait, une ressource de calcul telle que le caractère aléatoire n’a pas nécessairement une puissance de calcul fixe, qui soit "significative" ou "non significative".

Nous pouvons considérer que toute classe de complexité qui est basse pour lui-même - par exemple, , P , B P P , B Q P , ⊕ P ou P S P A C E - peut être appliquée à un modèle de machine dans lequel machine a toujours un état bien défini sur lequel vous pouvez poser des questions à tout moment, tout en permettant au calcul de continuer au-delà de la question que vous posez: en gros, la machine peut simuler un algorithme en tant que sous-programme pour un autre. La machine qui effectue le calcul peut ne pas être particulièrement réaliste$\mathsf L$$\mathsf P$$\mathsf{BPP}$$\mathsf{BQP}$$\mathsf{\oplus P}$$\mathsf{PSPACE}$si nous nous limitons à des contraintes pratiques sur les ressources ( par exemple  physiquement réalisables et capables de produire des réponses en temps polynomial de degré faible pour des problèmes d’intérêt), mais à la différence de classes telles que - pour lesquelles nous ne savons absolument pas comment une machine non déterministe pourrait produire la réponse à un autre problème de N $\mathsf{NP}$$\mathsf{NP}$et utiliser la réponse de quelque manière que ce soit en dehors des réductions de tables de vérité conjonctives et disjonctives (itérées) - imaginer qu'une telle classe soit incarnée par une machine à l'état bien défini sur lequel nous pouvons enquêter ne nous trompe pas.

Si nous adoptons cette position, nous pouvons nous demander ce qui se passera si nous fournissons à ces modèles de calcul des fonctionnalités supplémentaires telles que le caractère aléatoire ou le non-déterminisme. (Ces installations supplémentaires ne préservent pas nécessairement la propriété d'être interprétables par un modèle de machine, en particulier dans le cas du non déterminisme, mais donnent lieu à de «nouvelles» classes.) Si cette installation supplémentaire donne plus de puissance au modèle, pour une classe C , cela revient en fait à dire qu'il y a une réduction de C à M en utilisant cette facilité, par exemple  une réduction aléatoire dans le cas du caractère aléatoire.$\mathsf M$$\mathsf C$$\mathsf C$$\mathsf M$

La raison pour laquelle je décris cela en termes de classes qui sont faibles pour eux-mêmes est que si nous prenons au sérieux qu'ils sont des "modèles de calcul possibles dans un autre monde", votre question sur les réductions aléatoires correspond au fait qu'il semble que le hasard augmente considérablement la puissance de certains modèles mais pas d’autres .

Au lieu des réductions randomisées de à U P , on peut observer qu'il ya une réduction aléatoire de tous P H à la classe B P ⋅ ⊕ P - qui est obtenu si vous ajoutez aléatoire borné d'erreur à ⊕ P - par Théorème de Toda. Et votre question peut alors être posée comme suit : pourquoi cela se produit - il ? Pourquoi certaines machines devraient-elles gagner autant au hasard et d'autres si peu? Dans le cas de P H ⊆ B P ⋅ ⊕ $\mathsf{NP}$$\mathsf{UP}$$\mathsf{PH}$$\mathsf{BP\cdot\oplus P}$$\mathsf{\oplus P}$$\mathsf{PH} \subseteq \mathsf{BP\cdot\oplus P}$ , il semble que le non - déterminisme modulo-2 a entraîné dans la définition de (essentiellement un quantificateur de comptage modulo 2) catalyse le caractère aléatoire inhérent à une erreur bornée (essentiellement un quantificateur de comptage avec un écart de promesse) pour nous donner l’équivalent d’une hiérarchie entière et sans limite de quantificateurs existentiels et universels. Mais cela ne signifie pas que nous supposons que ⊕ P est lui-même approximativement aussi puissant que toute la hiérarchie polynomiale, n'est-ce pas? Ni les ressources d’aléatoire à erreur bornée ni la comptabilisation modulo-2 ne sont considérées comme aussi puissantes. Ce que nous observons, c’estqu’ensemble, ces deux quantificateurssontaussi puissants.$\mathsf{\oplus P}$$\mathsf{\oplus P}$

Il y a aussi une question de savoir si nous pouvons vraiment dire que le hasard est faible en termes absolus, comparé au non-déterminisme: si le hasard est si faible, et si nous sommes tellement convaincus que , pourquoi ne pouvons-nous lier que B P P ⊆ Σ p 2 ∩ ô p 2 dans la hiérarchie polynomiale, en utilisant deux niveaux d'indétermination, et encore moins un? Mais cela peut être simplement le résultat du fait que, bien que nous soupçonnions que le caractère aléatoire ajouté au calcul de temps polynomial simple ne donne pas beaucoup de puissance, nous n'avons aucune idée de la façon de simuler cette puissance supplémentaire en utilisant seulement une petite quantité de non-déterminisme du type impliqué. en $\mathsf{BPP} = \mathsf{P}$$\mathsf{BPP} \subseteq \Sigma^{\mathsf p}_2 \cap \Delta^{\mathsf p}_2$ et c o N P . (Bien sûr, il est difficile de prouverquoiquece soit qui nedérange pas dans la théorie de la complexité, mais làencore,c’est simplement l’affirmation que ces différents types de ressources sont difficiles à comparer sur une échelle!)$\mathsf{NP}$$\mathsf{coNP}$

Il n'y a pas d' argument fort que je peux donner pour défendre pourquoi cela devrait être le cas, autre que d'observer que jusqu'à présent simplement est le cas; et que si vous pensez que ne s'effondre pas, est différent de ⊕ P , et que B P P ≈ P , vous devez envisager la possibilité que des installations telles que le hasard et le non-déterminisme puissent avoir des pouvoirs difficilement comparables à un un autre, et qui peut se mettre en synergie ou se catalyser pour donner une puissance de calcul qu’aucun d’entre eux n’aurait de manière plausible. L'hypothèse que B P P = $\mathsf{PH}$$\mathsf{\oplus P}$$\mathsf{BPP} \approx \mathsf{P}$$\mathsf{BPP} = \mathsf{P}$Ce n’est pas que "l’aléatoire n’a pas de pouvoir", mais que l’aléatoire seul (ou plutôt, complété uniquement par un calcul de temps polynomial et fourni à un modèle de calcul par ailleurs déterministe) n’est pas puissant. Mais cela ne signifie pas qu'il ne peut y avoir de puissance aléatoire, qui pourrait être catalysée par d'autres ressources informatiques.