NP-intermédiaire
classe de complexité / De Wikipedia, l'encyclopédie encyclopedia
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.