NP-facile

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

Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, (ISBN 0-7167-1045-5), p. 117, 120.

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.