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, c`est le théorèm...