Decidir o vazio da interseção de idiomas regulares em tempo subquadrático

Seja dois idiomas regulares fornecidos pelos NFAs M_1 como entrada. $L_1,L_2$ $M_1,M_2$

Suponha que gostaríamos de verificar se . Isso pode ser feito claramente por um algoritmo quadrático que calcula o autômato do produto , , mas eu queria saber se algo mais eficiente é conhecido. $L_1\cap L_2\neq \emptyset$ $M_1,M_2$

Existe um algoritmo para decidir se ? Qual é o algoritmo mais rápido conhecido? $o(n^2)$ $L_1\cap L_2\neq \emptyset$

Se alguém tiver boas idéias, entre em contato, mas atualmente é um problema em aberto. Se você pudesse resolver esse problema em um tempo linear, basicamente qualquer problema solucionável por uma máquina não determinística usando apenas n bits de memória poderia ser resolvido deterministicamente em tempo.

2^{\frac{n}{2}}

$2^{\frac{n}{2}}$

Michael Wehar

Eu acho que ainda está aberto para qualquer sub-quadrático. Um pouco mais de informação: rjlipton.wordpress.com/2009/08/17/…

Michael Wehar

Assim, por exemplo (com base no comentário de Michael), a forte hipótese tempo exponencial implica que o expoente deve ser 2. Eu acho que isso também poderia provou a seguir a partir da hipótese tempo exponencial ...

Ryan Williams

RB: Suponha que você possa testar o vazio de dois DFAs de tamanho

no tempo

com

. Agora, se você tiver

DFAs de tamanho

, poderá criar o produto dos primeiros

DFAs e dos

DFAs restantes . Em seguida, teste o vazio no tempo

n

$n$

n^{1 + ε}

$n^{1+\varepsilon}$

ε < 1

$\varepsilon < 1$

k

$k$

n

$n$

k / 2

$k/2$

k / 2

$k/2$

melhor do que

. vzn: Este artigo premiado foi escrito por @MichaelWehar, que comentou neste tópico. Michael, talvez você possa enviar uma resposta, se tiver tempo!

(n^{k / 2})^{1 + ε} = n^{\frac{1}{2} k + \frac{ε}{2} k}

$(n^{k/2})^{1+\varepsilon} = n^{\frac{1}{2}k + \frac{\varepsilon}{2}k}$

n^{k}

$n^k$

quer

@RyanWilliams Oi Ryan, o que o leva a pensar que a hipótese de tempo exponencial mais fraco implica que não podemos resolver o não-vazio de interseção por dois DFAs mais rapidamente? Outra pessoa sugeriu isso para mim uma vez também. :)

Michael Wehar

Respostas:

Resposta simples : Se existe um algoritmo mais eficiente que é executado no tempo por alguns , a hipótese do tempo exponencial forte seria refutada. $O(n^{\delta})$ $\delta < 2$

Vamos provar um teorema mais forte e, em seguida, a resposta simples seguirá.

Teorema : Se pudermos resolver o problema de não-vazio de interseção por dois DFAs em tempo de , qualquer problema que seja solucionável de forma não determinística usando apenas n bits de memória será solucionável de forma determinística em tempo. $O(n^{\delta})$ $poly(n)\cdot2^{(\delta n/2)}$

Justificativa : suponha que possamos resolver o não vazio de interseção por dois DFAs em . Deixe uma máquina de Turing M não determinística com uma fita de entrada somente leitura e uma fita de trabalho binária de leitura / gravação. Seja dada uma string de entrada x de comprimento n. Suponha que M não acesse mais de n bits de memória na fita de trabalho binária. $O(n^{\delta})$

Um cálculo de M na entrada x pode ser representado por uma lista finita de configurações. Cada configuração consiste em um estado, uma posição na fita de entrada, uma posição na fita de trabalho e até n bits de memória que representam a fita de trabalho.

Agora, considere que a fita de trabalho foi dividida ao meio. Em outras palavras, temos uma seção esquerda de células e uma seção direita de $\frac{n}{2}$ $\frac{n}{2}$ $\frac{n}{2}$ $\frac{n}{2}$

$D_1$ $D_2$

$D_1$ $D_2$ $D_1$ $D_2$ $D_1$ $D_2$

$poly(n) \cdot 2^{n/2}$ $poly(n)$

$poly(n) \cdot 2^{(\delta n /2)}$

Você pode achar útil: https://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/

$k+O(\log(n))$ $O(n^{\delta})$ $poly(n) \cdot 2^{(\delta k/2)}$

Comentários, correções, sugestões e perguntas são bem-vindas. :)

Michael Wehar
fonte

Ω (n^{2})

$\Omega(n^2)$

k

$k$

k

$k$

(2 k - 2)

$(2k-2)$

k

$k$

N S p a c e (2 \cdot \log (n)) \subseteq D T i m e (n)

$NSpace(2 \cdot \log(n)) \subseteq DTime(n)$

N S p a c e (2 \cdot \log (n))

$NSpace(2 \cdot \log(n))$

2 \cdot \log (n)

$2\cdot \log(n)$ espaço para máquinas de Turing não determinísticas com uma fita de entrada somente leitura bidirecional e uma fita de trabalho binária bidirecional de leitura / gravação.

Michael Wehar