Generator pseudolosowy dla automatów skończonych

Niech będzie stałą. Jak możemy w sposób wiarygodny skonstruować pseudolosowy generator, który oszuka -state skończone automaty?$d$$d$

Tutaj automat skończony -state ma węzły, węzeł początkowy, zestaw węzłów reprezentujących stany akceptacji i dwie skierowane krawędzie oznaczone 0, 1 wychodzące z każdego węzła. Zmienia stan w naturalny sposób, odczytując dane wejściowe. Biorąc pod uwagę , znajdź takie, że dla każdego stanowego automatu skończonego obliczającego jakąś funkcję ,d ϵ f : { 0 , 1 } k → { 0 , 1 } n d $d$$d$$\epsilon$$f:\{0,1\}^{k}\to \{0,1\}^n$$d$$A$

Tutaj oznacza równomierny rozkład na zmiennych i chcemy, aby było jak najmniejsze (np. ). Myślę o tym, że jest rzędu , chociaż możemy również zadać pytanie bardziej ogólnie (np. Czy liczba wymaganych bitów wzrośnie z ?). k k log n d n $U_k$$k$$k$$\log n$$d$$n$$n$

Trochę tła

Konstrukcja generatorów pseudolosowych jest ważna w derandomizacji, ale ogólny problem (PRG w przypadku algorytmów wielomianowych) okazał się jak dotąd zbyt trudny. Poczyniono jednak postępy w zakresie PRG w zakresie obliczeń w przestrzeni ograniczonej. Na przykład ten ostatni artykuł ( http://homes.cs.washington.edu/~anuprao/pubs/spaceFeb27.pdf ) podaje granicę około dla zwykłych programów rozgałęziających do odczytu. Pytanie z ogólnymi programami do rozgałęziania do odczytu jest wciąż otwarte (z ), więc zastanawiam się, czy odpowiedź na to uproszczenie jest znana. (Automat skończony jest jak program do rozgałęziania, w którym raz czyta się, gdzie każda warstwa jest taka sama.)k = log $\log n\log d$$k=\log n$

Jeśli jest rzędu , możesz napisać program rozgałęziający o stałej szerokości jako automat stanu skończonego, a logarytmiczna długość ziarna nie jest znana.$d$$n$

Ale jeśli jest bardzo małe, powiedzmy stałą, wtedy możesz zrobić lepiej i osiągnąć logarytmiczną długość nasion - myślę, że to było coś, o czym myślałem lata temu, ale nigdy nie zapisałem. Sztuką jest użycie wyniku Nisana RL SC . Zasadniczo pokazuje, że jeśli otrzymujesz program rozgałęziający, możesz znaleźć rozkład logarytmiczny, który go oszuka. Jego wyniki obejmują niewielką liczbę programów rozgałęziających. Jeśli więc jest stałą, możesz wyliczyć wszystkie możliwe automaty skończone i znaleźć rozkład, który zmyli je wszystkie. Powinno to nadal działać, dopóki liczba programów jest wielomianowa w .⊆ d $d$$\subseteq$$d$$n$

wydaje się, że coś bliskiego temu, o co prosisz, zostało udowodnione w Thm 2.10 p6 tych notatek z wykładu O'Donnell, Wykład 16: PRG Nisana dla małej przestrzeni, ale nie przytacza oryginalnego ref. proste stwierdzenie tego twierdzenia w zakresie FSM nie jest podane w tej publikacji, ale jest możliwe do przetłumaczenia. Ochotnicy (?) w tw jest macierzą transformacji wyznaczającą FM. istnieją inne powiązane twierdzenia w notatkach.$M^n$

ten pozornie ten sam dowód przytacza także RJlipton na swoim blogu „gwarancja na generator Nisans” . dowód najwyraźniej pochodzi z artykułu Jak silny jest pseudolosowy generator Nisana? David, Papakonstantinou, Sidiropoulos (2010). zwróć również uwagę na prawie głębsze pytanie, a lepsze granice są powiązane z głównym podziałem klas złożoności:

Wskazują one na zewnątrz, bez dowodu, że gdyby było to nie wielomianowo PRG wózku i głupców logspace maszyny następnie .$\mathsf{L} \neq \mathsf{NP}$