Langage unaire

En théorie des langages, en théorie de la complexité, un langage unaire est un langage qui ne contient que des mots sur une seule et même lettre, généralement notée 1.

Exemple

{1, 11, 1111, 1111111} est un langage unaire.
{1^k | k est premier} est un langage unaire.

Théorie de la complexité

La classe de complexité de tous les langages unaires s'appelle TALLY. TALLY est inclus dans P/poly. En 1978, Berman[1] a montré que s'il existe un langage unaire qui est NP-complet, alors P = NP. Les langages unaires sont des langages creux, et ce résultat a été généralisé par Manahey aux langages creux[2] : s'il existe un langage creux qui est NP-complet, alors P = NP.

Notes et références

Piotr Berman. Relationship between density and deterministic complexity of NP-complete languages. In Proceedings of the 5th Conference on Automata, Languages and Programming, p. 63–71. Springer-Verlag. Lecture Notes in Computer Science #62. 1978.
S. R. Mahaney. Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis. Journal of Computer and System Sciences 25:130-143. 1982.

Portail de l’informatique
Portail des langues
Portail des mathématiques
Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] Piotr Berman. Relationship between density and deterministic complexity of NP-complete languages. In Proceedings of the 5th Conference on Automata, Languages and Programming, p. 63–71. Springer-Verlag. Lecture Notes in Computer Science #62. 1978.

[2] S. R. Mahaney. Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis. Journal of Computer and System Sciences 25:130-143. 1982.