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$ $d$ $\epsilon$ $f:\{0,1\}^{k}\to \{0,1\}^n$ $d$ $A$

| P_{x \sim U_{k}} (A (f (x)) = 1) - P_{x \sim U_{n}} (A (x) = 1) | < ϵ .

$|\mathbb P_{x\sim U_{k}}(A(f(x))=1)-\mathbb P_{x\sim U_n}(A(x)=1)|< \epsilon.$

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 ?). $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.) $\log n\log d$ $k=\log n$

automata-theory pseudorandomness pseudorandom-generators

— Holden Lee
źródło

może pomóc w szczegółowym / opisaniu, dlaczego jest to naturalne sformułowanie problemu, tj. pochodzenie / kg / szczegóły / rozumowanie wyrażenia prawdopodobieństwa. czy istnieją inne znane rozwiązania pytania dla innych modeli? czy jest to związane ze strukturą PAC itp.?

— vzn

Dodałem trochę tła.

— Holden Lee,

może pomysł zestawów oszukiwania FSM (p12) tutaj by się sprawdził? („Jeśli L ma nieskończony zestaw

— głupców

Odpowiedzi:

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$ $\subseteq$ $d$ $n$

— Manu
źródło

Myślę, że masz na myśli RL

SC.

\subseteq

$\subseteq$

— Holden Lee,

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}$

— vzn
źródło

zauważ, spójrz dalej, papier DPS jest rozszerzeniem papieru Nisansa [NIS92] w swoich odniesieniach do maszyn ograniczonych przestrzenią z wieloma przebiegami. tą referencją jest N. Nisan. Generatory pseudolosowe do obliczeń przestrzennych. Combinatorica, 12 (4): 449–461, 1992. (także STOC'90).

— vzn

Może jeśli przeczytasz artykuł Nisana, zauważysz, że wypowiada on swoje twierdzenie w zakresie FSM. Byłoby również miło, gdybyś podał pewne granice ilościowe

— Sasho Nikolov,

zwróć uwagę, że niektóre oświadczenia thm dotyczą TM logspace. patrz także Oszukiwanie modeli ograniczonych przestrzenią i wielomianów niskiego stopnia ankieta , Li, Yang, sec 1.3 p6 Oszukiwanie maszyny do odczytu log-space Turinga

— vzn

Zarówno to pytanie, jak i oryginalny artykuł zawierają oświadczenie dotyczące FSM. Twój komentarz jest więc mało istotny.

— Sasho Nikolov,

Czy możesz w swojej odpowiedzi podać odpowiednie twierdzenie w sformułowaniu FSM z pracy Nisana? Nie odnotowuje, że podaje się go w inny sposób, nie jest to artykuł ankietowy, który stwierdza, że jest inaczej: najpierw należy podać rzeczywistą odpowiedź na rzeczywiste pytanie ? Czy jest coś trudnego do zrozumienia, dlaczego warto to zrobić?

— Sasho Nikolov,