Chaque algorithme aléatoire peut être simulé par un algorithme déterministe, au détriment d'une augmentation exponentielle du temps d'exécution. La dérandomisation consiste à convertir des algorithmes aléatoires en algorithmes déterministes efficaces.
Une question récente de Huck Bennett demandant si la classe PH était contenue dans la classe PP, a reçu des réponses quelque peu contradictoires (tout à fait vrai, semble-t-il). D'un côté, plusieurs résultats Oracle ont été donnés, et de l'autre Scott a suggéré que la réponse était probablement...
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...
J'entends souvent dire que pour de nombreux problèmes, nous connaissons des algorithmes randomisés très élégants, mais pas, ou seulement des solutions déterministes plus compliquées. Cependant, je n'en connais que quelques exemples. Plus en évidence Tri rapide randomisé (et algorithmes géométriques...
Le théorème de Valiant-Vazirani dit que s'il existe un algorithme polynomial de temps (déterministe ou aléatoire) pour distinguer entre une formule SAT qui a exactement une affectation satisfaisante et une formule insatisfaisante - alors NP = RP . Ce théorème est prouvé en montrant que UNIQUE-SAT...
En une phrase: l'existence d'une hiérarchie pour impliquerait-elle des résultats de dérandomisation?BPTIMEBPTIME\mathsf{BPTIME} Une question connexe mais plus vague est: l'existence d'une hiérarchie pour implique-t-elle des limites inférieures difficiles? La résolution de ce problème heurte-t-elle...
Quels problèmes sont connus pour appartenir à mais ne sont pas connus pour appartenir à P ?BPPBPP\mathsf{BPP}PP\mathsf P Plus précisément, je m'intéresse aux problèmes indépendants , c'est-à-dire dont les dérandomisations ne sont pas connues pour être équivalentes. Par exemple, on sait que la...
RP est la classe de problèmes décidables par une machine de Turing non déterministe qui se termine en temps polynomial, mais qui est également autorisée en erreur unilatérale. P est la classe habituelle de problèmes décidables par une machine de Turing déterministe qui se termine en temps...
Je recherche des expandeurs déséquilibrés qui sont "bons" et "peu encombrants". Plus précisément, un graphe bipartite gauche-régulier , , , avec le degré gauche est un -expander si pour tout de taille au plus , le nombre de voisins distincts de dans est au moins. On sait que la méthode probabiliste...
Existe-t-il une bonne enquête qui compare différents extracteurs, concentrateurs et superconcentrateurs et présente les meilleures méthodes en termes de compromis entre le caractère aléatoire, le temps et l'espace?
Avec certains algorithmes randomisés, vous pouvez dérandomiser l'algorithme, en supprimant (à un coût possible en temps d'exécution) l'utilisation de bits aléatoires et en maximisant une limite inférieure sur l'objectif (généralement calculé en utilisant le fait que les théorèmes concernent les...
Alors que le théorème d'Adleman montre que , je ne connais aucune littérature qui étudie l'inclusion possible de . Quelles seraient les conséquences théoriques de la complexité d'une telle inclusion?BPP⊆P/polyBPP⊆P/poly\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}BQP⊆P/polyBQP⊆P/poly\mathsf{BQP}...
Considérons le modèle suivant: une chaîne de n bits r = r 1 ... r n est choisie uniformément au hasard. Ensuite, chaque indice i∈ {1, ..., n} est placé dans un ensemble A avec une probabilité indépendante 1/2. Enfin, un adversaire est autorisé, pour chaque i∈A séparément, à retourner r i s'il le...
Soit BPTIME(f(n))BPTIME(f(n))\mathsf{BPTIME}(f(n)) la classe des problèmes de décision ayant un algorithme aléatoire à erreur bilatérale borné fonctionnant dans le temps .O(f(n))O(f(n))O(f(n)) Connaît-on un problème tel que mais ? Sa non-existence est-elle prouvée? Q ∈ B P T I M E ( n k ) Q ∉ D T I...
Je suis intéressé par une fonction booléenne explicite avec la propriété suivante: si est constant sur un sous-espace affine de , alors la dimension de ce sous-espace est .f:0,1n→0,1f:0,1n→0,1f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}fff0,1n0,1n\\{0,1\\}^no(n)o(n)o(n) Il n'est pas difficile de...
Une distribution est dit ε -fool une fonction f si | E x ∈ U ( f ( x ) ) - E x ∈ D ( f ( x ) ) | ≤ ϵ . Et on dit qu'il trompe une classe de fonctions s'il trompe chaque fonction de cette classe. Il est connu que les espaces biaisés ϵ trompent la classe de parités sur les sous-ensembles. (voir...
J'ai trouvé le livre Pairwise Independence and Derandomization sur le sujet, mais il est plus axé sur la recherche que sur le tutoriel. Je suis nouveau sur le sujet de la "dérandomisation", et en tant que tel, je voulais savoir de quelle référence commencer? Je préfère celui qui traite de la...
Nisan a prouvé dans "Générateurs aléatoires pour le calcul délimité par l'espace", qu'il existe un générateur pseudo-aléatoire qui "trompe" les calculs délimités par l'espace. Cette construction est-elle valable pour chaque oracle (au moins pour les requêtes non
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"...
Adleman, FOCS'78 a montré que tout circuit randomisé pour des entrées de longueur peut être dérandomisé de manière non uniforme. Cependant, la construction duplique effectivement le circuit d'origine fois, de sorte que le circuit dérandomisé est plus grand que le circuit d'origine d'un facteur ....
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= BPPP=BPPP=BPP Le seul exemple qui me vient à l'esprit est le test de primalité polynomiale déterministe AKS...