Théorème de Mahaney

En informatique théorique, et plus précisément en théorie de la complexité, le théorème de Mahaney[1] dit que s'il existe un langage creux NP-complet, alors P = NP. Un langage creux est un langage où le nombre de mots de longueur n du langage est polynomial en n.

Références
  1. Stephen R. Mahaney, « Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis », Journal of Computer and System Sciences, vol. 25, no 2,‎ , p. 130–143 (DOI 10.1016/0022-0000(82)90002-2, 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.