Relation entre la complexité de l'algorithme et la classe des automates

Je n'ai pas pu trouver de graphique décrivant ou de texte répondant à la question suivante: Existe-t-il une relation directe entre la complexité d'un algorithme (tel que le meilleur / pire cas de tri rapide) et la classe d'automates qui peuvent implémenter l'algorithme. Par exemple, existe-t-il une gamme de complexité que les automates de refoulement peuvent exprimer? Si la réponse est oui à cette question, existe-t-il une ressource décrivant la relation? Merci!

Oui, il y a des relations dans de nombreux cas!

Par exemple, il est connu que tout langage accepté par les machines à compteur à bornes inversées est en $P$(voir ici ).

De même, nous savons que toutes les langues régulières sont $P$, car il existe un algorithme polynomial pour déterminer si un NFA accepte un mot donné.

Il y en a trop pour les énumérer ici, mais en général, les modèles de calcul plus limités sont dans des classes de complexité plus faciles.

Voici quelques résultats connus:

1. $\mathsf{REG} = \mathsf{DSPACE}(1) = \mathsf{NSPACE}(1) = \mathsf{DSPACE}(o(\log\log n)) = \mathsf{NSPACE}(o(\log\log n))$, où $\mathsf{REG}$est l'ensemble des langues régulières. Pour les preuves, voir la page Wikipedia sur$\mathsf{DSPACE}$.

2. $\mathsf{DCFL} \subseteq \mathsf{SC}$, où $\mathsf{DCFL}$ est l'ensemble des langages déterministes sans contexte, et $\mathsf{SC}$est la classe de Steve . Voir la page Wikipedia sur$\mathsf{DCFL}$.

3. $\mathsf{NL} \subseteq \mathsf{LOGCFL} \subseteq \mathsf{AC^1}$, où $\mathsf{LOGCFL}$est l'ensemble des langues réductibles en espace de journal en une langue sans contexte. Voir la page Wikipedia sur$\mathsf{LOGCFL}$, qui donne également des langues complètes pour $\mathsf{LOGCFL}$ sous réductions d'espace de journal.

4. $\mathsf{CSL} = \mathsf{NSPACE}(n)$, où $\mathsf{CSL}$est l'ensemble des langages contextuels. Voir la page Wikipedia sur$\mathsf{CSL}$.

5. La classe de langues acceptée par les PDA déterministes non effaçables est $\mathsf{DSPACE(n\log n)}$, et la classe de langues acceptée par les PDA non déterministes non déterministes est $\mathsf{NSPACE}(n^2)$. Voir la page Wikipedia sur les PDA .

6. Les automates à deux piles ont une puissance équivalente aux machines Turing, mais restreindre les automates entraîne des modèles plus faibles. Voir un rapport technique de San Pietro.

Existe-t-il une relation directe entre la complexité d'un algorithme (tel que le meilleur / pire des cas de tri rapide) et la classe d'automates qui peuvent implémenter l'algorithme.

La question de savoir quelle classe d'automates peut implémenter un algorithme donné comme le tri rapide est délicate, car on ne sait pas ce qui compterait comme une implémentation de cet algorithme. Pour un tri rapide, les comparaisons effectuées doivent certainement être les mêmes, mais l'ordre dans lequel les comparaisons se produisent doit-il également être le même? Qu'en est-il de l'ordre des accès en lecture à des éléments spécifiques de l'entrée? L'ordre des opérations de copie, de déplacement et d'échange pour des éléments spécifiques?

Vous devrez spécifier un certain nombre d' oracles pour les opérations qui vous importent, mais vous êtes déjà dans une situation très spécifique basée sur l'algorithme, et assez loin des classes générales d'automates généralement étudiées. Le moyen de contourner ce dilemme est de parler de problèmes plutôt que d'algorithmes, et de formaliser les problèmes en parlant de langages.

Par exemple, existe-t-il une gamme de complexité que les automates de refoulement peuvent exprimer?

Pas vraiment, car un automate poussé ne peut lire son entrée qu'une seule fois et uniquement dans le sens direct. Cependant, si vous divisez la machine en une partie qui est autorisée à lire l'entrée vers l'avant et vers l'arrière comme elle le souhaite, et conservez un nombre fini de pointeurs vers des positions d'entrée spécifiques (NL), et une partie qui est un automate poussant qui reçoit son entrée de l'autre partie, alors vous obtenez la classe de complexité LOGCFL , qui est égale à SAC ¹ (une classe de circuit).

Si vous ne séparez pas ces deux parties et d' ajouter juste une pile à NL, alors vous obtenez la classe des automates AuxPDA , ce qui équivaut à la classe de complexité P . Mais si vous décidez de limiter le temps d'exécution de ces automates (avec pile et stockage auxiliaire logarithmique) au temps polynomial, vous obtenez alors NAuxPDA ^P , qui est à nouveau égal à LOGCFL. (Et si vous insistez sur l'exécution polynomiale déterministe, supprimez la pile, mais autorisez le stockage auxiliaire polylogarithmique, alors vous obtenez SC .)

D'un autre côté, si vous gardez la restriction selon laquelle les automates ne peuvent lire son entrée qu'une seule fois et uniquement dans le sens direct, et exigez en outre qu'il ne puisse utiliser sa pile que d'une manière très déterministe directement basée sur l'entrée (c'est-à-dire le symbole d'entrée détermine si ces automates poussent quelque chose sur la pile, sautent quelque chose de la pile ou laissent la pile intacte), puis vous vous retrouvez avec un automate visiblement pushdown, qui reconnaît exactement les langages de mots imbriqués , qui peuvent également être reconnus dans l'espace logarithmique déterministe .