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