En informatique théorique, et plus précisément en théorie de la complexité, le théorème de Mahaney 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
Catégorie:Algorithmique Catégorie:Informatique théorique Catégorie:Logique mathématique