NP-difficile

Un article de Wikipédia, l'encyclopédie libre.

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.