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.