Langage creux
# 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. 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

Tous 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é

* 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.
