Aller au contenu

Théorème de Mahaney

Un article de Wikipédia, l'encyclopédie libre.
Ceci est la version actuelle de cette page, en date du 7 avril 2021 à 11:22 et modifiée en dernier par Wattcle (discuter | contributions). L'URL présente est un lien permanent vers cette version.
(diff) ← Version précédente | Voir la version actuelle (diff) | Version suivante → (diff)

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 | modifier le code]

  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 )
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Théorème_de_Mahaney&oldid=181651266 ».