NP-intermédiaire
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.
Description
Pour prouver ce théorème, Ladner a construit un problème artificiel sans application pratique. On ne sait pas si des problèmes naturels dans NPI existent, mais il existe un grand nombre de problèmes dont on ne sait pas dans quelle classe ils se trouvent[2]. Il en est ainsi de la décomposition en facteurs premiers.
Le théorème peut être formulé de sorte qu'il soit indépendant de l'hypothèse P ≠N P : Pour la réduction en temps polynomial (à la fois réduction de Turing et réduction many-one), il n'existe pas de classe minimale au-dessus de P. Cela signifie, en d'autres termes, que si un problème A est strictement plus difficile que les problèmes de P, alors il existe des problèmes B qui ne sont pas non plus dans P mais sont strictement plus faciles que A[3].
Notes et références
- 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 ).
- « Problems Between P and NPC » sur cstheory.stackexchange.com.
- Piergiorgio Odifreddi, Classical Recursion Theory, vol. II, Amsterdam, Elsevier, coll. « Studies in Logic and the Foundations of Mathematics » (no 143), , xvi + 949 (ISBN 0-444-50205-X, zbMATH 0931.03057).