Générateur pseudo-aléatoire pour automates finis

Soit une constante. Comment peut - on construire prouvablement un générateur pseudo - aléatoire que les fous -state automates finis?$d$$d$

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 chaque nœud. Il change d'état de manière naturelle lors de la lecture de l'entrée. Etant donné un , trouver telle sorte que pour tout automate fini state calculant une fonction ,d ϵ f : { 0 , 1 } k → { 0 , 1 } n d $d$$d$$\epsilon$$f:\{0,1\}^{k}\to \{0,1\}^n$$d$$A$

Ici désigne la distribution uniforme sur variables, et nous voulons que soit aussi petit que possible (par exemple ). Je pense que est de l'ordre de , bien que nous puissions également poser la question de manière plus générale (ex. Le nombre de bits requis croîtrait-il avec ?). k k log n d n $U_k$$k$$k$$\log n$$d$$n$$n$

Quelques antécédents

La construction de générateurs pseudo-aléatoires est importante dans la dérandomisation, mais le problème général (PRG pour les algorithmes à temps polynomial) s'est jusqu'à présent révélé trop difficile. Il y a cependant eu des progrès sur les PRG pour le calcul en espace borné. Par exemple, cet article récent ( http://homes.cs.washington.edu/~anuprao/pubs/spaceFeb27.pdf ) donne une limite d'environ pour les programmes de branchement réguliers à lecture unique. La question avec les programmes de branchement généraux à lecture unique est toujours ouverte (avec ), donc je me demande si la réponse à cette simplification est connue. (Un automate fini est comme un programme de branchement à lecture unique où chaque couche est la même.)$\log n\log d$$k=\log n$

Si est de l'ordre de vous pouvez écrire un programme de branchement de largeur constante en tant qu'automate à états finis et la longueur de graine logarithmique n'est pas connue.$d$$n$

Mais si est très petit, disons une constante, alors vous pouvez faire mieux et obtenir une longueur de graine logarithmique - je pense, c'est quelque chose auquel j'ai pensé il y a des années mais que je n'ai jamais noté. L'astuce consiste à utiliser le résultat de Nisan RL SC . Fondamentalement, il montre que si vous recevez un programme de branchement, vous pouvez trouver une distribution de graine logarithmique qui le trompe. Son résultat s'étend à un petit nombre de programmes de branchement. Donc, si est une constante, vous pouvez énumérer tous les automates à états finis possibles et trouver une distribution qui les trompe tous. Cela devrait encore fonctionner tant que le nombre de programmes est polynomial en .⊆ d $d$$\subseteq$$d$$n$

quelque chose de proche de ce que vous demandez semble être prouvé dans Thm 2.10 p6 de ces notes de cours par O'Donnell, leçon 16: PRG de Nisan pour les petits espaces, mais il ne cite pas la référence d'origine pour la preuve. un simple énoncé du théorème en termes de FSM n'est pas donné dans cette référence mais est traduisible. (volontaires?) dans le théorème est une matrice de transition définissant un FSM. il y a d'autres théorèmes liés dans les notes.$M^n$

cette preuve apparemment même est également citée par RJlipton sur son blog "la garantie sur le générateur Nisans" . la preuve provient apparemment de l'article Quelle est la force du générateur pseudo-aléatoire de Nisan? David, Papakonstantinou, Sidiropoulos (2010). Notez également une question presque plus profonde et de meilleures limites sont liées à une séparation de classe de complexité majeure:

Ils soulignent, sans aucune preuve, que s'il y avait un PRG qui effectue polynomialement de nombreuses passes et dupe les machines de l'espace de journalisation, alors .$\mathsf{L} \neq \mathsf{NP}$