Je lis le classique "Hardness vs Randomness" de Nisan et Wigderson. Soit , et fixer une fonction l : N → N . Ils définissent une famille de fonctions G = { G n : B l ( n ) → B n } pour être pseudo-aléatoires dans le cas pour chaque circuit de taille n que nous avonsB = { 0 , 1 }B={0,1}B=\{0,1\}l :...
Nous supposons que . Ensuite, le fait suivant est bien connu:G∈G(n,p),p=lnn+lnlnn+c(n)nG∈G(n,p),p=lnn+lnlnn+c(n)nG\in G(n,p),p=\frac{\ln n +\ln \ln n +c(n)}{n} Pr[G has a Hamiltonian cycle]=⎧⎩⎨⎪⎪10e−e−c(c(n)→∞)(c(n)→−∞)(c(n)→c)Pr[G has a Hamiltonian...
Je m'intéresse à la génération de nombres pseudo-aléatoires pour la cryptographie. Outre le chapitre 5 de Menezes / Oorschot / Vanstone ; Chapitre 8 de Stinson ; et le chapitre 3 de Goldreich , où pourrais-je trouver plus? Je m'intéresse aux principes généraux de conception des PRNG (propriétés...
Dans le document Natural Proofs de Razborov-Rudich , page 6, dans la partie, ils expliquent qu'il existe de "solides preuves de limites inférieures contre les modèles de circuits monotones " et comment elles s'intègrent dans l'image, il y a les phrases suivantes: Ici, le problème n'est pas la...
Il existe de nombreuses situations où une "preuve" randomisée est beaucoup plus facile qu'une preuve déterministe, l'exemple canonique étant le test d'identité polynomiale. Question : Existe-t-il des "théorèmes" mathématiques naturels où une preuve randomisée est connue mais pas une preuve...
Si balles sont placées dans cases de manière uniforme et aléatoire, la poubelle la plus lourde contient balles avec une forte probabilité. Dans "The Power of Simple Tabulation Hashing" , Pătraşcu et Thorup mentionnent que "les limites de Chernoff-Hoeffding pour les applications avec une...
ppp≤d≤d\le dbias(p)≜|Prx∈{0,1}n(p(x)=0)−Prx∈{0,1}n(p(x)=1)|>ϵbias(p)≜|Prx∈{0,1}n(p(x)=0)−Prx∈{0,1}n(p(x)=1)|>ϵbias(p) \triangleq |\Pr_{x\in\{0,1\}^n}(p(x)=0)-\Pr_{x\in\{0,1\}^n}(p(x)=1)| \gt \epsilon * Lorsque j'écris un polynôme aléatoire avec des variables de degré et n, vous pouvez penser...
Soit une constante. Comment peut - on construire prouvablement un générateur pseudo - aléatoire que les fous -state automates finis?dréddrédd Ici, un automate fini state a nœuds, un nœud de début, un ensemble de nœuds représentant des états acceptés et deux bords dirigés étiquetés 0, 1 sortant de...
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...
Je me demande ce qui se passerait si, dans la définition de (Hiérarchie polynomiale, voir, par exemple ici ), le rôle de N P serait remplacé par R P ?PHPHPHNPNPNPR PRPRP Il semble que nous pourrions encore construire une hiérarchie, de la même manière que est construit, juste en utilisant R P...
Pouvons-nous prouver un résultat de concentration net sur la somme des variables aléatoires exponentielles indépendantes, ie Soit des variables aléatoires indépendantes telles que . Soit . Pouvons-nous prouver des bornes de la forme . Cela suit directement si nous utilisons la forme de variance des...
Il existe 4 contraintes différentes que nous pouvons avoir lors de la définition de K-SAT aléatoire. 1) Le nombre total de littéraux dans une clause donnée est exactement K ou AT la plupart des K 2) Un littéral donné peut être utilisé avec ou sans remplacement dans la même clause (A ou A ou A) 3)...
Supposons que l'on ait un algorithme randomisé (BPP) UNEAA utilisant rrr bits de caractère aléatoire. Les moyens naturels d'amplifier sa probabilité de réussite à 1 - δ1−δ1-\delta , pour tout δ> 0δ>0\delta>0 choisi , sont Exécutions indépendantes + vote majoritaire: exécutez UNEAA...
Il est bien connu que les formules CNF peuvent être grossièrement partitionnées en 2 grandes classes: aléatoire vs structurée. Les formules CNF structurées, contrairement aux formules CNF aléatoires, présentent une sorte d'ordre, montrant des modèles qui ne se produiront probablement pas par...
Quelle est la complexité temporelle exacte de l' algorithme d'espace de journalisation st-connectivité non orienté d'Omer
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...
B P PBPP\mathsf{BPP} etZPPZPP\mathsf{ZPP} sont deux des classes de complexité probabiliste de base. BPPBPP\mathsf{BPP} est la classe de langages décidée par les algorithmes de Turing à temps polynomial probabiliste où la probabilité que l'algorithme renvoie une réponse incorrecte est limitée,...
Laissez la classe BPNC (la combinaison de et N C ) être des algorithmes parallèles de profondeur de journal avec une probabilité d'erreur bornée et un accès à une source aléatoire (je ne suis pas sûr que cela ait un nom différent). Définissez la classe DBPNC de la même manière, sauf que tous les...
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...
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