Adleman a montré en 1978 que BPP⊆P/polyBPP⊆P/poly\mathrm{BPP}\subseteq \mathrm{P/poly} : si une fonction booléenne fff de nnn variables peut être calculée par un circuit booléen probabiliste de taille MMM , alors fff peut également être calculé par un circuit booléen déterministe de taille polynôme...
Les inégalités de type Chernoff sont utilisées pour montrer que la probabilité qu'une somme de variables aléatoires indépendantes s'écarte significativement de sa valeur attendue est exponentiellement faible dans la valeur attendue et l'écart. Existe-t-il une inégalité de type Chernoff pour toute...
Étant donné (iid gaussiens avec moyenne et variance ), est-il possible (comment?) D'échantillonner (pour ) Y_1, \ ldots, Y_m tels que les Y_i sont des gaussiens indépendants par paire avec moyenne 0 et variance 1 .X1,…,XkX1,…,XkX_1,\ldots,X_k000111m=k2m=k2m=k^2Y1,…,YmY1,…,YmY_1, \ldots,...
Les algorithmes de flux nécessitent la randomisation pour la plupart pour ne rien faire de non trivial, et en raison de la contrainte de petit espace, ont besoin de PRG qui utilisent peu d'espace. Je connais deux méthodes qui ont été citées jusqu'à présent dans les algorithmes de flux: F 2 ℓ 2kkk...
Il est connu que l'ajout d'une randomisation à erreurs bornées à PSPACE n'ajoute pas de puissance. Autrement dit, BPPSAPCE = PSPACE. On ne sait pas si P = BPP, mais on sait que .B PP⊆ Σ2∩ Π2BPP⊆Σ2∩Π2BPP\subseteq \Sigma_2\cap \Pi_2 Ainsi, il est possible (bien que supposé être faux) que l'ajout de...
Compte tenu composite N∈NN∈NN\in\Bbb N tamis de champ numérique général est le meilleur algorithme de factorisation connu pour factorisation entier de NNN . Il s'agit d'un algorithme randomisé et nous obtenons une complexité attendue de
Je lisais un article intitulé Random Oracles with (out) Programmability . Le dernier paragraphe de la section 2.3 se lit comme suit: [En utilisant notre nouvelle approche], il n'est pas nécessaire d'appliquer des techniques classiques de dérandomisation asymptotique (et uniforme) bien connues...
J'ai quelques questions concernant la tromperie des circuits à profondeur constante. On sait que logO(d)(n)logO(d)(n)\log^{O(d)}(n) sens de l'indépendance est nécessaire pour tromper AC0AC0AC^0 circuits AC ^ 0 de profondeur ddd , où nnn est la taille de l'entrée. Comment peut-on le prouver?...
Je lis le fameux article Impagliazzo et Wigderson en 1997. Comme je suis nouveau dans ce domaine et que l'article est une version concise de la conférence, j'ai du mal à suivre leurs épreuves. En particulier, certains de leurs nouveaux théorèmes manquent de preuves. À ma connaissance, aucune...
J'ai développé une nouvelle technique de dérandomisation qui vise des algorithmes randomisés récursifs (ou) plus généralement des algorithmes randomisés qui utilisent une pile. Malheureusement, je n'ai pas pu trouver d'algorithmes aléatoires naturels pour appliquer mes techniques. Les chaînes de...
Étant donné telle sorte que les coefficients de p , q soient bornés par B , est-ce que p ≡ q est vrai ?p(x1,…,xn),q(x1,…,xn)∈Z[x1,…,xn]p(x1,…,xn),q(x1,…,xn)∈Z[x1,…,xn]p(x_1,\dots,x_n),q(x_1,\dots,x_n)\in \Bbb Z[x_1,\dots,x_n]p,qp,qp,qBBBp≡qp≡qp\equiv q Le lemme de Schwartz-Zippel s'applique ici car...
Dans les tests d'identité polynomiale, nous recherchons un algorithme déterministe pour déduire l'égalité de deux polynômes . Dérandomiser des algorithmes randomisés efficaces connus et produire un algorithme déterministe efficace est un problème ouvert important. Existe-t-il un problème complet...
L'inclusion inverse est évidente, tout comme le fait que tout langage NP auto-réductible dans BPP l'est également dans RP. Est-ce également connu pour les langages NP non
Soit k > 0k>0k>0 une constante fixe. Etant donné un entier nnn , nous voulons construire une permutation σ∈ Snσ∈Sn\sigma \in S_n telle que: La construction utilise un temps et un espace constants (c'est-à-dire que le prétraitement prend un temps et un espace constants). Nous pouvons utiliser...
Par BPP / linéaire, je me réfère aux machines BPP avec conseil linéaire, qui remplissent la promesse quand on leur donne le conseil "correct", et la dérandomisation devrait nous donner, disons, un algorithme P / linéaire ou (SUBEXP / linéaire). Si nous utilisons des hypothèses non uniformes, je...
Il semble y avoir de nombreux algorithmes randomisés pour les tests d'identité polynomiale, vérifiant si un polynôme donné est nul ou non. Y a-t-il des résultats d'algorithmes qui font une sorte d'estimation des polynômes sur un ensemble spécifique de points? Cela pourrait être, par exemple, une...
Je m'intéresse à des exemples de constructions dans la théorie de la complexité qui sont meilleures que des constructions aléatoires. Le seul exemple d'une telle construction que je connaisse est dans le domaine des codes correcteurs d'erreurs. Les codes à géométrie algébrique sont meilleurs dans...
Le calcul d'une machine de Turing non déterministe (NTM) est bien connu pour être représentable comme un arbre de configurations, enraciné à la configuration de départ. Toute transition dans le programme est représentée par un lien père-enfant dans cet arbre. Des arbres similaires peuvent également...
Que soit une classe de complexité et BP- C la contrepartie aléatoire de C défini de la même manière que BPP est défini par rapport à P . Plus formellement, nous fournissons polynomialement de nombreux bits aléatoires et nous acceptons une entrée si la probabilité d'accepter est supérieure à...