NP-facile

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Cet article ne cite pas suffisamment ses sources (août 2018).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

Dans la théorie de la complexité, un problème est NP-facile s'il est résoluble en temps polynomial par une machine de Turing déterministe avec oracle, pour un certain problème de décision dans NP.

En d'autres termes, un problème X est NP-facile si et seulement si il existe un problème Y de NP tel que X est réductible en temps polynomiale à Y.^[1] Cela signifie qu'étant donné un oracle pour Y, il existe un algorithme qui résout X en temps polynomial (éventuellement en utilisant cet oracle de manière répétée).

NP-facile est une autre appellation pour FP^NP ou pour FΔ₂P (voir l'article sur la hiérarchie polynomiale).

Un exemple d'un problème NP-facile est le problème de tri d'une liste de chaînes de caractères. Le problème de décision "La chaîne A est plus longue que la chaîne B" est dans NP. Il existe des algorithmes tels que le tri rapide qui permettent de trier la liste en utilisant seulement un nombre polynomial d'appels à la routine de comparaison. Par conséquent, le tri est NP-facile.

Références

• Portail des mathématiques