Langage creux
En théorie de la complexité, un langage creux est un langage où le nombre de mots de longueur n est borné par un polynôme en n. Ils sont utiles dans l'étude de la classe NP[1]. L'adjectif creux illustre bien un tel langage : sur un alphabet à deux lettres, comme il y a 2 n mots de longueur n, alors s'il n'y a qu'un nombre polynomial de mots de longueur n, cela signifie que la proportion de mots de longueur n dans un langage creux tend vers 0, quand n tend vers l'infini.
Exemples
modifierTous les langages unaires (i.e. les langages dont les mots s'écrivent sur une seule lettre) sont creux. Le langage des mots sur l'alphabet {0, 1} où il y a exactement k occurrences de 1 est un langage creux.
Lien avec les classes de complexité
modifier- Si tout langage creux est coNP-complet, alors P = NP.
- Si tout langage creux est NP-complet, alors P = NP (Théorème de Mahaney).
- S'il existe un langage creux P-complet, alors L = P.
Notes et références
modifier- (en) Steven Fortune, « A Note on the Sparse Complete Sets », Technical Report, Cornell University, (lire en ligne, consulté le )
