Aller au contenu

NP-difficile

Un article de Wikipédia, l'encyclopédie libre.
Ceci est une version archivée de cette page, en date du 22 janvier 2018 à 17:45 et modifiée en dernier par Jules* (discuter | contributions). Elle peut contenir des erreurs, des inexactitudes ou des contenus vandalisés non présents dans la version actuelle.

Cet article court présente un sujet plus développé dans : Problème NP-complet.

En informatique théorique, un problème NP-difficile est un problème vers lequel on peut ramener tout problème de la classe NP par une réduction polynomiale.

S'il est également dans la classe NP, on dit que c'est un problème NP-complet.

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=NP-difficile&oldid=144737606 ».