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 modifier
- 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 )
