Décider de la vacuité de l'intersection des langues régulières en temps sub-quadratique

Soit deux langues régulières données par les NFA en entrée. $L_1,L_2$ $M_1,M_2$

Supposons que nous souhaitons vérifier si . Cela peut clairement être fait par un algorithme quadratique qui calcule l'automate produit de , mais je me demandais si quelque chose de plus efficace était connu. $L_1\cap L_2\neq \emptyset$ $M_1,M_2$

Existe-t-il un algorithme pour décider si ? Quel est l'algorithme le plus rapide connu? $o(n^2)$ $L_1\cap L_2\neq \emptyset$

Si quelqu'un a de bonnes idées, faites-le moi savoir, mais actuellement c'est un problème ouvert. Si vous pouviez résoudre ce problème en un temps linéaire, alors tout problème résolu par une machine non déterministe utilisant uniquement n bits de mémoire pourrait être résolu de manière déterministe en temps.

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

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

Michael Wehar

Je pense qu'il est toujours ouvert pour tout sous-quadratique. Quelques informations supplémentaires: rjlipton.wordpress.com/2009/08/17/…

Michael Wehar

Ainsi, par exemple (basé sur le commentaire de Michael), l'hypothèse de temps exponentielle forte implique que l'exposant devrait être 2. Je pense que cela pourrait également se révéler découler de l'hypothèse de temps exponentiel ...

Ryan Williams

RB: Supposons que vous pouvez tester le vide de deux DFA de taille dans le temps avec . Maintenant, si vous avez DFA de taille , vous pouvez créer le produit des premiers DFA et des DFA restants . Ensuite, testez le vide dans le temps qui est mieux que . vzn: Ce document primé a été écrit par @MichaelWehar qui a commenté dans ce fil. Michael, vous pourriez peut-être soumettre une réponse, si vous en avez le temps!

n

$n$

n^{1 + ε}

$n^{1+\varepsilon}$

ε < 1

$\varepsilon < 1$

k

$k$

n

$n$

k / 2

$k/2$

k / 2

$k/2$

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

Michael Blondin

@ RyanWilliams Salut Ryan, qu'est-ce qui vous fait penser que l'hypothèse de temps exponentiel plus faible implique que nous ne pouvons pas résoudre plus rapidement le non-vide d'intersection pour deux DFA? Quelqu'un d'autre me l'a suggéré une fois aussi. :)

Michael Wehar

Réponse simple : s'il existe un algorithme plus efficace qui s'exécute en temps pour un certain , alors l'hypothèse de temps exponentiel fort serait réfutée. $O(n^{\delta})$ $\delta < 2$

Nous prouverons un théorème plus fort et ensuite la réponse simple suivra.

Théorème : si nous pouvons résoudre le problème de non-vacuité d'intersection pour deux DFA en temps , alors tout problème non résolvable de manière déterministe en utilisant seulement n bits de mémoire est résolvable de manière déterministe en heure. $O(n^{\delta})$ $poly(n)\cdot2^{(\delta n/2)}$

Justification : Supposons que nous pouvons résoudre la non-vacuité d'intersection pour deux DFA en temps . Soit une machine de Turing non déterministe M avec une bande d'entrée en lecture seule et une bande de travail binaire en lecture / écriture. Soit une chaîne d'entrée x de longueur n donnée. Supposons que M n'accède pas à plus de n bits de mémoire sur la bande de travail binaire. $O(n^{\delta})$

Un calcul de M sur l'entrée x peut être représenté par une liste finie de configurations. Chaque configuration comprend un état, une position sur la bande d'entrée, une position sur la bande de travail et jusqu'à n bits de mémoire qui représentent la bande de travail.

Maintenant, considérez que la bande de travail a été divisée en deux. En d'autres termes, nous avons une section gauche de cellules et une section droite de cellules . Chaque configuration peut être décomposée en une pièce gauche et une pièce droite. La partie gauche se compose de l'état, de la position sur la bande d'entrée, de la position sur la bande de travail et des bits de la section gauche. La bonne pièce se compose de l'état, de la position sur la bande d'entrée, de la position sur la bande de travail et des bits de la section de droite. $\frac{n}{2}$ $\frac{n}{2}$ $\frac{n}{2}$ $\frac{n}{2}$

Maintenant, nous construisons un DFA dont les états sont des morceaux de gauche et un DFA dont les états sont des morceaux de droite. Les caractères alphabétiques sont des instructions qui indiquent dans quel état aller, comment les têtes de bande doivent se déplacer et comment la cellule active de la bande de travail doit être manipulée. $D_1$ $D_2$

L'idée est que et lisent une liste d'instructions correspondant à un calcul de M sur l'entrée x et vérifient ensemble qu'elle est valide et acceptante. Les deux et seront toujours d' accord sur l' endroit où les têtes de bande sont parce que l' information est inclus dans leurs caractères d'entrée. Par conséquent, nous pouvons demander à vérifier que l'instruction est appropriée lorsque la position du ruban de travail est dans la pièce de gauche et vérifier lorsqu'elle est dans la pièce de droite. $D_1$ $D_2$ $D_1$ $D_2$ $D_1$ $D_2$

Au total, il existe au plus états pour chaque DFA et au plus caractères alphabétiques distincts. $poly(n) \cdot 2^{n/2}$ $poly(n)$

Par l'hypothèse initiale, il s'ensuit que nous pouvons résoudre le non-vide d'intersection pour les deux DFA en temps . $poly(n) \cdot 2^{(\delta n /2)}$

Vous pourriez trouver cela utile: https://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/

CNF-SAT peut être résolu en utilisant bits de mémoire où k est le nombre de variables. La construction précédente peut être utilisée pour montrer que si nous pouvons résoudre le non-vide d'intersection pour deux DFA en temps , alors nous pouvons résoudre CNF-SAT en heure. Par conséquent, la réponse simple est valable. $k+O(\log(n))$ $O(n^{\delta})$ $poly(n) \cdot 2^{(\delta k/2)}$

Les commentaires, corrections, suggestions et questions sont les bienvenus. :)

Michael Wehar
la source

tous très bien, mais la question initiale ci-dessus était pour les NFA; tout suit-il encore? aussi, certains détails clés sont omis. semble valoir un papier. ou est-ce que tout est dans votre publication? si c'est le cas, citez-le / liez-le à des théorèmes numérotés, etc., il serait également utile de le préciser davantage en termes de classes de complexité standard L, P, NP, PSpace, ExpTime, etc. si possible. se demandant également si quelque chose peut être dit à propos de la direction "forte" de l'intersection DFA à 2 voies, borne inférieure ( ?) → SETH ...? que faut-il montrer pour cela?

Ω (n^{2})

$\Omega(n^2)$

vzn

Salut VZN, le problème d'intersection pour les NFA semble légèrement plus difficile que le problème d'intersection pour les DFA. Cependant, ce n'est pas le cas car il y a une réduction paramétrée de la non-vacuité d'intersection pour NFA à la non-vacuité d'intersection pour DFA. Ceci est mentionné dans mon premier article.

k

$k$

k

$k$

Michael Wehar

Vous pouvez peut-être décrire plus en détail ce que vous voulez dire lorsque vous mentionnez DFA bidirectionnel. Le problème de non-vide pour les DFA bidirectionnels est tout aussi difficile que le problème de non-vide d'intersection pour DFA unidirectionnels. Lien: cs.stackexchange.com/questions/13456/…

(2 k - 2)

$(2k-2)$

k

$k$

Michael Wehar

En termes de classes de complexité standard, vous pouvez indiquer ceci comme quelque chose comme: implique que SETH est faux. Lorsque j'écris , je veux dire un espace pour les machines de Turing non déterministes avec une bande d'entrée en lecture seule bidirectionnelle et un binaire en lecture / écriture bidirectionnel bande de travail.

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

Michael Wehar

Décider de la vacuité de l'intersection des langues régulières en temps sub-quadratique

Réponses: