Pseudozufallsgenerator für endliche Automaten

12

Sei eine Konstante. Wie können wir ein Pseudo - Zufalls konstruieren beweisbar Generator , dass Narren d -state endliche Automaten?dd

Hier hat ein endlicher Automat mit Zuständen d Knoten, einen Startknoten, eine Menge von Knoten, die Akzeptanzzustände darstellen, und zwei gerichtete Kanten, die mit 0, 1 bezeichnet sind und aus jedem Knoten kommen. Es ändert den Zustand auf natürliche Weise, während es Eingaben liest. Wenn ein ϵ gegeben ist , finde f : { 0 , 1 } k{ 0 , 1 } n, so dass für jeden endlichen d- Zustand-Automaten eine Funktion A berechnet wird ,ddϵf:{0,1}k{0,1}ndA

|PxUk(A(f(x))=1)PxUn(A(x)=1)|<ϵ.

Hier bezeichnet die gleichmäßige Verteilung auf k Variablen, und wir möchten, dass k so klein wie möglich ist (z . B. log n ). Ich denke, dass d in der Größenordnung von n liegt , obwohl wir die Frage auch allgemeiner stellen können (zum Beispiel, würde die Anzahl der benötigten Bits mit n wachsen ?).Ukkklogndnn

Etwas Hintergrund

Die Konstruktion von Pseudozufallsgeneratoren ist bei der Derandomisierung wichtig, aber das allgemeine Problem (PRGs für Polynomzeitalgorithmen) hat sich bisher als zu schwierig erwiesen. Es wurden jedoch Fortschritte bei PRGs für die Berechnung des begrenzten Raums erzielt. Zum Beispiel gibt dieses kürzlich erschienene Papier ( http://homes.cs.washington.edu/~anuprao/pubs/spaceFeb27.pdf ) eine Grenze von ungefähr für reguläre Verzweigungsprogramme mit einmaligem Lesen an. Die Frage mit allgemeinen Verzweigungsprogrammen zum einmaligen Lesen ist noch offen (mit k = log n ), daher frage ich mich, ob die Antwort für diese Vereinfachung bekannt ist. (Ein endlicher Automat ist wie ein einmal lesbares Verzweigungsprogramm, bei dem jede Ebene gleich ist.)lognlogdk=logn

Holden Lee
quelle
Es könnte hilfreich sein, einige der Gründe, warum dies eine natürliche Formulierung des Problems ist, im Detail zu beschreiben, dh die Ursprünge / bkg / Details / Gründe des Wahrscheinlichkeitsausdrucks. gibt es andere bekannte lösungen der frage für andere modelle? ist es mit dem PAC-Framework usw. verbunden?
vzn
Ich habe einen kleinen Hintergrund hinzugefügt.
Holden Lee
Vielleicht würde die Idee von FSM-Dummköpfen (S. 12) hier gut funktionieren? ("Wenn L eine unendliche Menge von Narren hat, dann wird L von keinem DFA akzeptiert.")
vzn

Antworten:

10

Wenn in der Größenordnung von liegtd , können Sie ein Verzweigungsprogramm mit konstanter Breite als endlichen Automaten schreiben, und die logarithmische Keimlänge ist nicht bekannt.n

Aber wenn sehr klein ist, sagen wir eine Konstante, dann können Sie es besser machen und eine logarithmische Samenlänge erreichen - ich denke, das ist etwas, worüber ich vor Jahren nachgedacht habe, aber es wurde nie aufgeschrieben. Der Trick besteht darin, Nisans Ergebnis RL SC zu verwenden . Grundsätzlich zeigt er, dass Sie, wenn Sie ein Verzweigungsprogramm erhalten, eine logarithmische Keimverteilung finden können, die es täuscht. Sein Ergebnis erstreckt sich auf eine kleine Anzahl von Verzweigungsprogrammen. Wenn also d eine Konstante ist, können Sie alle möglichen Automaten mit endlichen Zuständen aufzählen und eine Verteilung finden, die alle täuscht. Dies sollte immer noch funktionieren, solange die Anzahl der Programme in n polynomial ist .ddn

Manu
quelle
Ich denke du meinst RL SC.
Holden Lee
1

Etwas in der Nähe dessen, was Sie wünschen, scheint in Thm 2.10 p6 dieser Vorlesungsnotizen von O'Donnell, Vorlesung 16: Nisans PRG für kleinen Raum , bewiesen zu sein, zitiert aber nicht die ursprüngliche Referenz für den Beweis. Eine einfache Aussage des Theorems in Bezug auf FSMs ist in dieser Literaturstelle nicht gegeben, aber übersetzbar. (Freiwillige?) im Satz Mn ist eine Übergangsmatrix, die eine FSM definiert. es gibt andere verwandte Sätze in den Anmerkungen.

Dieser anscheinend gleiche Beweis wird auch von RJlipton in seinem Blog "Die Garantie auf Nisans Generator" zitiert . Der Beweis stammt anscheinend aus der Zeitung. Wie stark ist Nisans Pseudo-Zufallsgenerator? David, Papakonstantinou, Sidiropoulos (2010). Beachten Sie auch, dass eine tiefere Frage und bessere Grenzen mit einer großen Trennung der Komplexitätsklassen verbunden sind:

LNP

vzn
quelle
Beachten Sie außerdem, dass das DPS-Papier eine Erweiterung des Nisans-Papiers [NIS92] in Bezug auf raumbegrenzte Maschinen mit mehreren Durchgängen ist. dieser Hinweis ist N. Nisan. Pseudozufallsgeneratoren für raumbegrenzte Berechnungen. Combinatorica, 12 (4): 449–461, 1992. (auch STOC'90).
VZN
1
Wenn Sie Nisans Zeitung lesen, werden Sie vielleicht feststellen, dass er seinen Satz in Bezug auf FSMs formuliert. Auch wäre es schön, wenn Sie einige quantitative Grenzen geben
Sasho Nikolov
Beachten Sie, dass einige Aussagen des thm sich auf Logspace-TMs beziehen. siehe auch Fooling space-bounded models und low degree
polynoms eine umfrage
Sowohl diese Frage als auch das Originalpapier geben eine Aussage in Bezug auf FSMs. Ihr Kommentar ist also kaum relevant.
Sasho Nikolov
2
Können Sie in Ihrer Antwort den relevanten Satz in der FSM-Formulierung aus Nisans Aufsatz angeben? Keine Notizen, die es anders ausdrücken, keine Umfrage, die es anders ausdrücken: Geben Sie zuerst die eigentliche Antwort auf die eigentliche Frage an ? Ist etwas schwer zu verstehen, warum das eine gute Sache ist?
Sasho Nikolov