Corrija um número inteiro e alfabeto . Defina como a coleção de todos os autômatos de estados finitos em estados com o estado inicial 1. Estamos considerando todos os DFAs (não apenas os conectados, mínimos ou não degenerados); assim, .
Agora, considere duas cordas e definir para ser o número de elementos de que aceitar ambos e .
Pergunta: Qual é a complexidade da computação ?
Esta questão tem implicações para o aprendizado de máquina .
Edit: Agora que há uma recompensa sobre esta questão, suponho que um pouco mais de precisão na formulação esteja em ordem. Para , seja D F A ( n ) a coleção de n 2 n 2 n autômatos, conforme definido acima. Para x , y ∈ { 0 , 1 } * , definir K N ( x , y ) para ser o número de autómatos em D F A ( n ) que aceitar tanto e . Pergunta: ser calculado no tempo ?
Respostas:
Portanto, a pergunta é bem breve, mas muito interessante. Suponho que a entrada seja em unário e e em binário (ou temos problemas, como apontado pela resposta de Kai).x yn x y
Antes de tudo, se você estiver interessado em conhecer aproximadamente, poderá gerar alguns DFA aleatórios e isso fornecerá a você (whp) uma boa aproximação. (Gostaria de saber se essa classe de complexidade tem um nome.)K(x,y)
Então, conhecer parece exatamente um problema difícil. Como fora apontado nos comentários por a3_nm e Kaveh, a questão é equivalente a determinação do número de autômatos para o qual e ir para o mesmo estado. Denotarei a probabilidade de que eles cheguem ao mesmo estado na .x y pK(x,y) x y p
Atualização: Algumas das coisas que escrevi aqui não eram verdadeiras, agora as corrigi.
É fácil ver que . Temos igualdade, se é todos os 0 e é zero, exceto seu último bit, que é um 1. Existem outros casos? Eu não sei. Se, por exemplo, for a sequência vazia e , então .x y x y = 00 p = n + 1p≥1/n x y x y=00 p=n+1(n−1)n
Para simplificar o problema, eu mesmo comecei a pensar sobre o que acontece se e são unário. Se ambos são pelo menos e sua diferença é divisível por, então . Existe uma fórmula simples para a versão unária?y n n ! p = 1x y n n! p=1
fonte
Talvez eu esteja perdendo o objetivo, mas você declarou que é fixo, portanto todos os DFAs desse tamanho podem ser considerados pré-computados e armazenados em um formato facilmente simulável. Calcule K da seguinte maneira:n K
Na entrada , y onde x , y ∈ Σ ∗x y x,y∈Σ∗
uma. simule-o em ambas as palavras (esta etapa é )O(|xy|)
b. incremento se ambas as execuções de simulação estiverem aceitandoc
Ao todo, a computação tem complexidade linear. A resposta é bem diferente para .K(n,x,y)
fonte