Théorème de Mahaney
# 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 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.

