Gerador pseudoaleatório para autômatos finitos

Seja uma constante. Como podemos comprovadamente construir um gerador pseudo-aleatório que engana os autômatos finitos do estado ? $d$ $d$

Aqui, um -state finito autómatos tem nodos, um nó de início, um conjunto de nodos que representam aceitar os estados, e duas arestas dirigidas rotulado 0, 1 saindo de cada nó. Ele muda de estado da maneira natural à medida que lê a entrada. Dado um , encontre tal que para todo autômato finito do estado computa alguma função , $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.$

Aqui denota a distribuição uniforme em variáveis, e nós queremos ser tão pequeno quanto possível (por exemplo, ). Estou pensando em estar na ordem de , embora também possamos fazer a pergunta de maneira mais geral (por exemplo, o número de bits necessários aumentaria com ?). $U_k$ $k$ $k$ $\log n$ $d$ $n$ $n$

Alguma experiência

A construção de geradores pseudo-aleatórios é importante na derandomização, mas o problema geral (PRG's para algoritmos de tempo polinomial) até agora se mostrou muito difícil. No entanto, houve progresso nos PRGs para computação em espaço limitado. Por exemplo, este artigo recente ( http://homes.cs.washington.edu/~anuprao/pubs/spaceFeb27.pdf ) fornece um limite de aproximadamente para programas regulares de ramificação de leitura única. A questão com os programas gerais de ramificação de leitura única ainda está aberta (com ), portanto, estou me perguntando se a resposta para essa simplificação é conhecida. (Um autômato finito é como um programa de ramificação de leitura única, onde cada camada é a mesma.) $\log n\log d$ $k=\log n$

automata-theory pseudorandomness pseudorandom-generators Holden Lee
fonte

pode ajudar a detalhar / descrever alguns motivos pelos quais essa é uma formulação natural do problema, isto é, as origens / bkg / details / raciocínio da expressão de probabilidade. existem outras soluções conhecidas da pergunta para outros modelos? está vinculado à estrutura do PAC etc?

vzn

Eu adicionei um pouco de fundo.

Holden Lee

talvez a idéia de conjuntos de enganação FSM (p12) funcionasse bem aqui? ("Se L tem um conjunto infinito de enganos, então L não é aceito por nenhum DFA.")

vzn

Respostas:

$d$ $n$

$d$ $\subseteq$ $d$ $n$

Manu
fonte

\subseteq

$\subseteq$

$M^n$

aparentemente essa mesma prova também é citada por RJlipton em seu blog "a garantia do gerador de nisans" . a prova aparentemente se origina no artigo Qual é a força do gerador pseudo-aleatório de Nisan? David, Papakonstantinou, Sidiropoulos (2010). Observe também uma pergunta mais profunda e limites melhores estão associados a uma grande separação de classes de complexidade:

$\mathsf{L} \neq \mathsf{NP}$

vzn
fonte

observe, mais adiante, o papel DPS é uma extensão do papel Nisans [NIS92] em suas referências a máquinas com espaço limitado com várias passagens. essa referência é N. Nisan. Geradores pseudo-aleatórios para computação em espaço limitado. Combinatorica, 12 (4): 449-461, 1992. (também STOC'90).

vzn

Talvez se você ler o artigo de Nisan, perceberá que ele afirma seu teorema em termos de FSMs. Também seria bom se você der alguns limites quantitativos

Sasho Nikolov

observe que algumas declarações thm estão em termos de TMs do espaço de log. ver também modelos limitada de espaço enganando e polinômios baixos graus de pesquisa , Li, Yang, sec 1,3 p6 Fooling leitura uma vez log-space Máquina de Turing

vzn

Tanto essa questão quanto o artigo original dão uma declaração em termos de FSMs. Portanto, seu comentário não é relevante.

Sasho Nikolov

Você pode apenas declarar o teorema relevante, na formulação FSM do artigo de Nisan, em sua resposta? Não observa que a afirmam de maneira diferente, nem um documento de pesquisa que afirma de outra maneira: primeiro indique a resposta real à pergunta real ? Existe algo difícil de entender sobre por que isso é uma coisa boa a se fazer?

Sasho Nikolov