NP-difficile

Carte Commune · n° 211341

En théorie de la complexité, un problème NP-difficile est un problème appartenant à la classe NP-difficile, ce qui revient à dire qu'il est au moins aussi difficile que les problèmes les plus difficiles de la classe NP. Ainsi, un problème H est NP-difficile, si tout problème L de la classe NP peut être réduit en temps polynomial à H. Si un problème NP-difficile est dans NP, alors c'est un problème NP-complet. Donc tous les problèmes NP-complets sont NP-difficiles.

Lire sur Wikipédia · Image Behnam Esfahbod, CC BY-SA 3.0