Algorithme randomisé qui «semble» déterministe?

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

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 .$\mathbb{Z}_p^*$$p$$2q + 1$$q$

(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 .$n$$2n$

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 .$n$$2n$

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(\log n)$

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.

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 .$2^n$$n$$2^n$

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 .$2^{n-1}$

Est-ce admissible?

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.$\mathbb{F}_p$$\log p$$p$

$\log p$

Il y avait un projet polymath répondant à une question connexe: http://michaelnielsen.org/polymath1/index.php?title=Finding_primes

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.

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:

$\rm{ZPP}$$\rm{RP}$$\rm{ZPP}$$\rm{NP}$$\rm{NP} \cap \rm{coNP}$

$\frac{1}{n^c}$$\text{polylog}(n)$