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

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.

Notes et références
  1. (en) Steven Fortune, « A Note on the Sparse Complete Sets », Technical Report, Cornell University,‎ (lire en ligne, consulté le )
  • Portail des mathématiques
  • Portail de l’informatique
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.