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, n^o 1,‎ janvier 1975, p. 155–171 (DOI 10.1145/321864.321877, lire en ligne, consulté le 16 juillet 2017).
« 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 » (n^o 143), 1999, xvi + 949 (ISBN 0-444-50205-X, zbMATH 0931.03057).

Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] Richard E. Ladner, « On the Structure of Polynomial Time Reducibility », Journal of the ACM, vol. 22, n^o 1,‎ janvier 1975, p. 155–171 (DOI 10.1145/321864.321877, lire en ligne, consulté le 16 juillet 2017).

[2] « Problems Between P and NPC » sur cstheory.stackexchange.com.

[3] Piergiorgio Odifreddi, Classical Recursion Theory, vol. II, Amsterdam, Elsevier, coll. « Studies in Logic and the Foundations of Mathematics » (n^o 143), 1999, xvi + 949 (ISBN 0-444-50205-X, zbMATH 0931.03057).