NP-intermédiaire

Un article de Wikipédia, l'encyclopédie libre.
Ceci est une version archivée de cette page, en date du 29 juillet 2020 à 23:36 et modifiée en dernier par Herr Satz (discuter | contributions). Elle peut contenir des erreurs, des inexactitudes ou des contenus vandalisés non présents dans la version actuelle.

En théorie de la complexité, un problème NP-intermédiaire est un problème dans NP, qui n'est ni NP-complet et ni dans P. La classe des problèmes NP-intermédiaires se note NPI. Richard Emil Ladner a démontré en 1975, que sous l'hypothèse que P ≠ NP, NPI est non vide[1], c'est le théorème de Ladner.

Histoire

Idées des démonstrations

Notes et références

  1. ↑ Richard E. Ladner, « On the Structure of Polynomial Time Reducibility », Journal of the ACM, vol. 22, no 1,‎ , p. 155–171 (DOI 10.1145/321864.321877, lire en ligne, consulté le ).
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=NP-intermédiaire&oldid=173397068 ».