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
- 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 )
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.