Complexité informatique vs hiérarchie de Chomsky

Je m'interroge sur la relation entre la complexité de calcul et la hiérarchie de Chomsky, en général.

En particulier, si je sais qu'un problème est NP-complet, cela signifie-t-il que la langue de ce problème n'est pas sans contexte?

Par exemple, le problème de clique est NP-complet. S'ensuit-il que le langage correspondant aux modèles avec des cliques est d'une complexité minimale dans la hiérarchie de Chomsky (pour toutes / certaines façons de coder les modèles sous forme de chaînes?)

Il existe quatre classes de langue dans la hiérarchie Chomsky:

1. Langues régulières - cette classe est la même que ou T I M E ( o ( n log n ) ) (défini à l'aide de machines à bande unique, voir le commentaire d'Emil), ou S P A C E ( 0 ) ou S P A C E ( o ( log log n ) ) (selon le commentaire d'Emil).$\mathrm{TIME}(n)$$\mathrm{TIME}(o(n\log n))$$\mathrm{SPACE}(0)$$\mathrm{SPACE}(o(\log\log n))$

2. Langues sans contexte - cette classe n'a pas de belles propriétés de fermeture, donc à la place, on considère généralement $\mathrm{LOGCFL}$ , la classe des langues réductibles en espace de journal aux langues sans contexte. Il est connu que se trouve dans A C 1 (et donc, en particulier, dans P ), et il a de beaux problèmes complets détaillés dans l'article lié.$\mathrm{LOGCFL}$$\mathrm{AC}^1$$\mathrm{P}$

3. Langages contextuels - cette classe correspond à .$\mathrm{NSPACE}(n)$

4. Grammaires illimitées - cette classe comprend toutes les langues énumérables récursivement.

Si un langage en NP-complet suppose alors P NP, il n'est pas sans contexte. Cependant, cela pourrait être contextuel (clique et SAT le sont tous les deux). Toute langue dans NP est décrite par une grammaire illimitée.$\neq$