Algorithme randomisé qui «semble» déterministe?

31

Existe-t-il un exemple intéressant d'algorithme randomisé pour un problème de recherche qui génère toujours la même réponse (correcte), indépendamment de son caractère aléatoire interne, mais qui exploite le caractère aléatoire de sorte que son temps d'exécution attendu soit meilleur que le temps d'exécution du plus rapide connu algorithme déterministe pour le problème?

En particulier, je me demandais s'il existe un tel algorithme pour trouver un nombre premier entre n et 2n. Il n'y a pas d'algorithme déterministe du temps polynomial connu. Il existe un algorithme aléatoire aléatoire qui fonctionne simplement en échantillonnant des entiers aléatoires dans l'intervalle, qui fonctionne grâce au théorème des nombres premiers . Mais existe-t-il un algorithme du type ci-dessus dont le temps de fonctionnement attendu est intermédiaire entre les deux?

EDIT: Pour affiner légèrement ma question, je voulais un tel algorithme pour un problème où il existe de nombreuses sorties correctes possibles, et pourtant l'algorithme randomisé se fixe sur une indépendante de son caractère aléatoire. Je me rends compte que la question n'est probablement pas entièrement spécifiée ...

Arnab
la source
3
Pour vous donner des mots clés de recherche, les algorithmes randomisés qui produisent toujours la bonne réponse (et utilisent le caractère aléatoire pour un temps d'exécution plus court) sont appelés algorithmes de Las Vegas (par opposition aux algorithmes de Monte Carlo) ou algorithmes sans erreur, et une classe de complexité associée est ZPP .
Tsuyoshi Ito
@Tsuyoshi: Merci pour votre commentaire. Mais je ne connais pas les algorithmes de type Las Vegas pour les problèmes de recherche. Telle est ma question.
arnab
S'il existe un algorithme aléatoire pour trouver des équilibres Nash uniques qui répondraient à votre question.
Warren Schudy
Peut-être y a-t-il un problème lié aux attaques d'anniversaire ( en.wikipedia.org/wiki/Birthday_attack ) qui répondrait à vos besoins?
Warren Schudy

Réponses:

23

Shafi Goldwasser m'a communiqué qu'elle et ses co-auteurs avaient étudié exactement de tels algorithmes pour les problèmes de théorie des nombres! Ce qui suit est connu:

  1. Lenstra a montré qu'il existe un tel algorithme pour trouver un mod quadratique non résiduel d'un nombre premier donné.

  2. Gat et Goldwasser ont montré qu'il existe un tel algorithme pour trouver un générateur de , où p est un nombre premier donné de la forme 2 q + 1 pour un nombre premier q .Zpp2q+1q

(Je ne connais pas de références citées.) Il y a aussi des recherches en cours sur la question que j'ai posée sur la recherche d'un nombre premier entre et 2 n .n2n

EDIT: L'article de Gat et Goldwasser est maintenant publié: http://eccc.hpi-web.de/report/2011/136/ . Cet article ne résout cependant pas la question de trouver un nombre premier entre et 2 n .n2n

arnab
la source
1
Virtuel +1. C'est vraiment intéressant, va chercher le papier.
András Salamon
2
Malgré la note, j'ai voté pour cette réponse simplement parce que c'est une bonne réponse. Je ne pense pas qu'il y ait quelque chose de mal à voter une bonne réponse publiée pour quelqu'un d'autre. J'ai commencé une discussion sur Meta à ce sujet.
Tsuyoshi Ito
1
J'ai supprimé la note et en ai fait un "wiki communautaire" conformément à la discussion sur le fil méta.
arnab
Le méta thread mentionné par arnab peut être trouvé ici: meta.cstheory.stackexchange.com/q/607/873 .
MS Dousti
18

Les structures de données randomisées comptent-elles?

Il y a la liste de saut qui est une structure de données de carte associative triée.

Son temps d'exécution pour les opérations courantes telles que l'insertion, la récupération et la suppression est (dans le cas attendu) comparable à celui des arbres de recherche équilibrés - c'est-à-dire . Cependant, la structure de données est parfois revendiquée comme ayant un bien meilleur facteur constant que les implémentations d'arbres de recherche lorsqu'elle est effectuée correctement (cela dépend de manière critique d'une bonne et efficace source de caractère aléatoire). Le meilleur facteur constant résulte probablement du fait qu'aucun rééquilibrage (ou toute opération similaire) ne doit avoir lieu.O(logn)

Konrad Rudolph
la source
Merci! Cela compte vraiment et c'est une réponse non triviale à ma question initiale. Je voulais un problème bien que plus analogue au problème de recherche de prime, où il existe de nombreuses solutions potentielles.
arnab
Ajoutez des listes de sauts à ce courant de pensée.
Raphael
13

Qu'en est-il de l'algorithme simplex à temps polynomial randomisé de Kelner et Spielman? Il trouve le sommet optimal d'un programme linéaire. Aucun algorithme simplex déterministe connu ne fonctionne en temps polynomial, et pour beaucoup d'entre eux, des instances pathologiques peuvent être construites qui font que l'algorithme prend un temps exponentiel.

Bien sûr, il existe des algorithmes de point intérieur en temps polynomial, donc ce n'est pas exactement ce que vous recherchez.

Peter Shor
la source
S'il y a plusieurs points optimaux, Kelner-Spielman retournerait-il toujours le même point?
Sasho Nikolov
3
Les programmes linéaires génériques n'ont qu'un seul point optimal, donc en utilisant la perturbation, une variante de Kelner-Spielman pourrait être faite qui renvoie toujours le même point optimal.
Peter Shor
12

Considérons un arbre binaire complet avec les feuilles contenant 0, sauf une feuille qui en contient 1. La tâche consiste à trouver la feuille qui contient 1. Contre tout algorithme de recherche déterministe, il est possible de construire une famille infinie d'arbres (un pour chaque n ) pour lequel l'algorithme doit vérifier chaque feuille. Ainsi, pour cette famille du pire des cas, l'algorithme déterministe a prévu une durée d'exécution de 2 n .2nn2n

Considérons maintenant un algorithme qui choisit au hasard la première feuille de façon uniforme et aléatoire, puis vérifie toutes les feuilles successives de manière déterministe (en remontant au début). Cela trouvera le 1 après avoir examiné la moitié de toutes les feuilles, en moyenne. Ainsi, l'algorithme randomisé a attendu l'exécution .2n1

Est-ce admissible?

András Salamon
la source
Agréable!! Cela se qualifie certainement, bien que je cherchais un exemple plus trivial où l'amélioration du temps de fonctionnement est plus substantielle.
arnab
Vous n'avez pas besoin de la structure arborescente, cela fonctionne sur un tableau.
sdcvvc
7

Les algorithmes de factorisation polynomiale peuvent être le type d'exemple que vous recherchez. L' algorithme de Cantor-Zassenhaus utilise l'aléatoire pour calculer les facteurs polynomiaux irréductibles (jusqu'à une échelle unique) d'un polynôme univarié donné sur un champ fini en polynôme temporel de la taille de l'entrée et du log p . Si vous voulez vraiment que le problème ait une réponse unique, vous pouvez demander les facteurs premiers moniques irréductibles d'un polynôme monique. Pour autant que je sache, on ne sait pas comment factoriser le temps polynomial déterministe à moins que p ne soit garanti d'être petit.Fplogpp

logp

Srikanth
la source
3

Concernant votre première question, j'ai d'abord pensé à Quicksort mais cela devrait être évident.

Il existe un algorithme de correspondance de chaînes ( Nebel, 2006 ) qui utilise des idées probabilistes. Je sais cependant si c'est l'approche la plus rapide qui existe, et vous avez apparemment besoin de quelques échantillons pour vous entraîner.

Raphaël
la source
La médiane est également plus rapide, mais pas de façon spectaculaire.
Aram Harrow
3

Le document STACS '97 suivant peut être intéressant pour votre cas: La complexité de la génération d'instances de test .

Résumé: Récemment, Watanabe a proposé un nouveau cadre pour tester l'exactitude et le comportement de cas moyen des algorithmes qui prétendent résoudre un problème de recherche NP donné efficacement en moyenne. L'idée est de générer au hasard des instances certifiées d'une manière qui ressemble à la distribution sous-jacente. Nous discutons de cette approche et montrons que des instances de test peuvent être générées pour chaque problème de recherche NP avec des requêtes non adaptatives sur un oracle NP. De plus, nous présentons les types de générateurs d'instances de test de Las Vegas ainsi que de Monte Carlo et montrons que ces générateurs peuvent être utilisés pour savoir si un algorithme est correct et efficace en moyenne. En fait, il n'est pas difficile de construire des générateurs Monte Carlo pour tous les problèmes de recherche RP ainsi que des générateurs Las Vegas pour tous les problèmes de recherche ZPP. D'autre part,

Surtout, jetez un œil à la page 384, sous Corollaire 12:

ZPPRPZPPNPNPcoNP

MS Dousti
la source
2

1ncpolylog(n)

Ramprasad
la source
3
Il s'agit de tester et de ne pas trouver ...
Dana Moshkovitz
Je m'intéressais davantage aux problèmes de recherche. Pour les problèmes de décision, il existe des algorithmes de Las Vegas.
arnab