L'aléatoire est un élément clé des algorithmes probabilistes, de nombreux arguments combinatoires, de l'analyse des fonctions de hachage et de la cryptographie, entre autres applications.
Je cherche une réponse définitive à la question de savoir si la génération de nombres "réellement aléatoires" est calculable par Turing. Je ne sais pas comment formuler cela avec précision. Cette question de StackExchange sur les "algorithmes efficaces pour la génération de nombres aléatoires" est...
J'ai récemment entendu ceci: "Une machine non déterministe n'est pas la même chose qu'une machine probabiliste. En gros, une machine non déterministe est une machine probabiliste dans laquelle les probabilités de transitions ne sont pas connues". Je me sens comme si je comprends le point mais je...
Récemment, Gil Kalai et Dick Lipton ont tous deux écrit un bel article sur une hypothèse intéressante proposée par Peter Sarnak, expert en théorie des nombres et Hypothèse de Riemann. Conjecture. Soit la fonction de Möbius . Supposons que soit une fonction avec entrée sous la forme d'une...
Beaucoup pensent que . Cependant, nous savons seulement que est dans le deuxième niveau de la hiérarchie polynomiale, c'est-à-dire . Un pas vers montrant B P P = P est d'abord de faire descendre au premier niveau de la hiérarchie polynomiale, soit B P P ⊆ N P .BPP=P⊆NPBPP=P⊆NP\mathsf{BPP} =...
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...
Un ordinateur doté d'un flux infini de bits vraiment aléatoires est plus puissant qu'un ordinateur sans un. La question est: est-elle suffisamment puissante pour résoudre le problème de l'arrêt? Autrement dit, un ordinateur probabiliste peut-il déterminer si un programme déterministe s'arrête ou...
En relation avec le puzzle Slither Link , je me suis demandé: supposons que j'ai une grille de cellules carrées et que je souhaite trouver un cycle simple de bords de grille, uniformément au hasard parmi tous les cycles simples possibles.n×nn×nn\times n Une façon de le faire serait d'utiliser une...
Dans un article scientifique de 2002, Mezard, Parisi et Zecchina ont proposé l' heuristique de propagation de croyances pour 3SAT aléatoire. Les expériences indiquent que l'heuristique fonctionne bien pour les ratios de contraintes par variable pour lesquels une affectation satisfaisante est...
Luca Trevisan a montré combien de constructions de générateurs pseudo-aléatoires peuvent en fait être considérées comme des constructions d'extracteurs: http://www.cs.berkeley.edu/~luca/pubs/extractor-full.pdf Y a-t-il une conversation significative? C'est-à-dire, les constructions "naturelles" des...
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?
Existe-t-il un moyen (raisonnable) d'échantillonner une fonction booléenne uniformément aléatoire dont le degré en tant que polynôme réel est au plus ?dF: { 0 , 1 }n→ { 0 , 1 }f:{0,1}n→{0,1}f:\{0,1\}^n \to \{0,1\}rédd EDIT: Nisan et Szegedy ont montré qu'une fonction du degré dépend au plus de...
Y a-t-il un exemple d'un problème naturel qui est dans BPP mais qui n'est pas connu pour être RP ou
Si est une fonction convexe, l'inégalité de Jensen indique que , et mutatis mutandis lorsque est concave. De toute évidence, dans le pire des cas, vous ne pouvez pas dépasser la limite en termes de pour un convexe , mais existe-t-il une limite qui va dans ce sens si est convexe mais "pas trop...
Y a-t-il eu des recherches sur la mise en œuvre de constructions d'extracteurs aléatoires? Il semble que les preuves d'extraction utilisent Big-Oh, laissant la possibilité de grandes constantes cachées, rendant les implémentations programmatiques potentiellement irréalistes. Un peu de contexte: je...
Est - il possible de construire un explicite 0 / 1 matrix avec N 1,5 ceux de telle sorte que tous les N 0,499 × N 0,499 sous - matrice contient moins de N 0,501 celles?N× NN×NN \times N 0 / 10/10/1N1,5N1.5N^{1.5}N0,499× N0,499N0.499×N0.499N^{0.499} \times N^{0.499}N0,501N0.501N^{0.501} Ou il est...
Deux questions connexes sur l'informatique en profondeur limitée: 1) Supposons que vous commenciez par n bits et que vous commenciez par le bit i peut être 0 ou 1 avec une certaine probabilité p (i), indépendamment. (Si cela rend le problème plus simple, nous pouvons supposer que tous les p (i) s...
Dans cette question , nous semblons avoir identifié un problème naturel qui est NP-complet sous des réductions aléatoires, mais peut-être pas sous des réductions déterministes (bien que cela dépende des hypothèses non prouvées dans la théorie des nombres qui sont vraies). Existe-t-il d'autres...
Cette question est inspirée du t-shirt du Georgia Tech Algorithms and Randomness Center , qui demande "Randomize or not ?!" Il existe de nombreux exemples où la randomisation est utile, en particulier lors d'opérations dans des environnements contradictoires. Il existe également certains paramètres...
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...
Pour autant que je sache, la plupart des implémentations de la génération de nombres pseudo-aléatoires utilisent des méthodes telles que les registres de rétroaction à décalage linéaire (LSFR), ou ces algorithmes "Mersenne Twister". Bien qu'ils passent de nombreux tests statistiques (heuristiques),...