NP-intermédiaire

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

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

Idées des démonstrations[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. Richard E. Ladner, « On the Structure of Polynomial Time Reducibility », J. ACM, vol. 22, no 1,‎ , p. 155–171 (ISSN 0004-5411, DOI 10.1145/321864.321877, lire en ligne)