Exemples de dérandomisation réussie de BPP à P

Quels sont quelques exemples majeurs de dérandomisation réussie ou du moins de progrès dans la démonstration de preuves concrètes vers l' objectif (pas la connexion de dureté aléatoire)? $P=BPP$

Le seul exemple qui me vient à l'esprit est le test de primalité polynomiale déterministe AKS (même pour cela, il y avait une méthodologie supposant GRH). Alors, quelles preuves spécifiques par exemple avons-nous pour la dérandomisation (encore une fois pas la dureté ou la connexion Oracle)?

Veuillez ne conserver des exemples que dans les cas où l' amélioration de la complexité temporelle a été montrée, du poly aléatoire au poly déterministe ou quelque chose de très proche pour des problèmes spécifiques.

Ce qui suit est plus un commentaire et je ne sais pas grand-chose cela aidera cette requête.

Chazelle a une déclaration très intrigante dans http://www.cs.princeton.edu/~chazelle/linernotes.html sous «The Discrepancy Method: Randomness and Complexity (Cambridge University Press, 2000)».

«Cela a été une source infinie de fascination pour moi qu'une compréhension plus approfondie du calcul déterministe devrait nécessiter la maîtrise de la randomisation. J'ai écrit ce livre pour illustrer cette puissante connexion. Des arbres couvrant le minimum à la programmation linéaire en passant par les triangulations de Delaunay, les algorithmes les plus efficaces sont souvent des dérandomisations de solutions probabilistes. La méthode des écarts met en lumière l'une des questions les plus fructueuses de toute l'informatique: si vous pensez avoir besoin de bits aléatoires, dites-nous pourquoi?

cc.complexity-theory big-list randomized-algorithms derandomization pseudorandom-generators
la source

De nombreux algorithmes peuvent être dérandomisés à l'aide de techniques générales comme la méthode des attentes conditionnelles, la méthode des estimateurs pessimistes et l'utilisation d'espaces d'échantillonnage d'indépendance bornés. En fait, les tests de primalité et les tests d'identité polynomiale sont si célèbres parce qu'ils sont de rares exemples de fonctions naturelles qui résistent aux techniques de dérandomisation standard.

Sasho Nikolov

@SashoNikolov merci, le commentaire pourrait être développé en tant que réponse complète sur certains exemples. La connexion dureté-aléatoire via la complexité du circuit est-elle la seule raison pour laquelle les gens croient

P = B P P

$P=BPP$

Je pense que c'est un peu trop basique pour une réponse. Voir le chapitre sur la dérandomisation dans Alon-Spencer pour des détails et des exemples: il couvre les trois techniques que j'ai mentionnées.

Sasho Nikolov

La chose intéressante à propos de la classe BPP est que sa définition théorique nécessite des bits d'entrée aléatoires qui peuvent être facilement montrés, en utilisant la dé-randomisation et des mesures de hasard aléatoires kolomogrov faibles, pour ne pas exister dans des domaines finis. Je ne sais pas comment les gens peuvent vivre avec cette incohérence. Je ne crois pas moi-même qu'il existe un BPP de classe explicite (c'est soit NP soit P).

Réponses:

. $SL = L$

signifie espace journal randomisé et est une version plus petite du problème $RL$ $RL=L$ . Un important tremplin est la preuve de Reingold en '04 ( « non dirigé ST connectivité dans LOGSPACE ») que , où signifie « symétrique » et est une classe intermédiaire entre et . $RP=P$ $SL = L$ $S$ $SL$ $RL$ $L$

L'idée est que vous pouvez considérer une machine de Turing à espace de journalisation aléatoire comme un graphe orienté de taille polynomiale, où les nœuds sont des états de la machine, et un algorithme RL effectue une marche aléatoire qui a de bonnes propriétés. SL correspond aux graphiques non orientés de cette forme. La preuve de Reingold s'est appuyée sur des travaux sur des graphiques d'extenseur, en particulier le "produit en zigzag" de Reingold, Vadhan et Wigderson, pour prendre n'importe quelle marche aléatoire sur un graphique non dirigé avec de bonnes propriétés et le transformer en une promenade aléatoire conservant ces propriétés.

modifier cette question a été publiée avant que la question ne soit explicitement modifiée pour se concentrer exclusivement sur P vs BPP ... Je laisse de côté car cela semble être intéressant.

usul
la source

Je vous en prie, ne le faites pas. La réponse est intéressante.

Emil Jeřábek soutient Monica

Salut @Student., Je pense que les personnes venant à la question intéressées par des exemples de dérandomisation réussie seront intéressées par cette réponse, donc je la garderai, sans vouloir manquer de respect à vos objectifs (qui n'ont été édités que plus tard pour spécifier la complexité du temps ... )

usul

Je dois également dire que les questions et réponses sur ce site sont censées être formulées de manière à être généralement utiles aux futurs visiteurs en tant que ressource de référence, et pas seulement pour répondre aux objectifs particuliers de l'affiche. Pour ma part, je trouve la question sans restrictions artificielles à la complexité du temps et BPP beaucoup plus utile.

Emil Jeřábek soutient Monica

@ EmilJeřábek Ok merci, nous laisserons le post de usul tel qu'il est ici.

@usul 'L'idée est que vous pouvez considérer une machine de Turing à espace de journalisation aléatoire comme un graphique dirigé de taille polynomiale'. Y a-t-il une intuition appropriée qui fonctionne pour NL? Je sais que L n'est pas NL est conjecturé mais PSPACE = NPSPACE et donc l'espace peut être différent du temps.

T ....

Il n'y a fondamentalement qu'un seul problème intéressant dans BPP non connu pour être dans P: Test d'identité polynomiale, étant donné qu'un circuit algébrique est le polynôme qu'il génère de manière identique à zéro. Impagliazzo et Kabanets montrent que PIT en P impliquerait des limites inférieures de circuit. Donc, les limites inférieures du circuit sont la seule raison (mais assez bonne) que nous croyons P = BPP.

Lance Fortnow
la source

Bien que je sois d'accord avec vous à un niveau élevé, je pense que la pléthore d'algorithmes randomisés dans la théorie des groupes de calcul suggère une autre classe étroitement liée de questions intéressantes de dérandomisation, qui ne semblent pas se réduire à PIT. Alors que la plupart d'entre elles sont des fonctions plutôt que des problèmes de décision, certains d'entre eux peuvent être refondus en tant que problèmes de décision intéressants dans BPP, par exemple cstheory.stackexchange.com/a/11440/129

Joshua Grochow

O (f (n))

$O(f(n))$

O (f (n))

$O(f(n))$

B P P

$BPP$

B P P

$BPP$

f (n)

$f(n)$

P = B P P

$P=BPP$

Outre les tests d'identité polynomiale, un autre problème très important connu pour être dans BPP mais pas dans P est d'approximer le permanent d'une matrice non négative ou même le nombre de correspondances parfaites dans un graphique. Il existe un algorithme poly-temps randomisé pour approximer ces nombres dans un facteur (1 + eps), tandis que les meilleurs algorithmes déterministes n'atteignent que ~ 2 ^ n facteurs approximatifs.

Bien que permanent soit l'exemple principal, il existe de nombreux problèmes de comptage approximatifs pour lesquels il existe un énorme fossé entre les algorithmes randomisés (généralement basés sur les méthodes «MCMC») et les algoritmes déterministes.

Un autre problème dans une veine similaire consiste à approximer le volume d'un corps convexe explicitement donné (disons un polyèdre décrit par une collection d'inégalités linéaires).

Raghu Meka
la source

Une subtilité dans P vs BPP, que j'aimerais mieux comprendre, est la différence entre les problèmes de fonction et les problèmes de décision. Il se peut qu'il existe de nombreux problèmes de fonction pouvant être résolus (dans un certain sens) de manière aléatoire mais non déterministe en temps polynomial, mais P = BPP. Il semble que vos exemples se traduisent probablement facilement par des problèmes de décision, n'est-ce pas?

usul

Les problèmes de décision par rapport à la fonction sont un peu plus subtils que dans le monde NP, mais on en sait encore beaucoup: par exemple, cet article de la section 3 donne un exemple de "problème de recherche résolvable poly temps aléatoire" qui n'est même pas décidable. Mais si la fonction est biunivoque, alors P = BPP implique qu'un "problème de fonction résoluble en temps poly aléatoire" a un algorithme déterministe en temps poly (le papier donne aussi beaucoup d'autres exemples)

Joe Bebel