NP-hardnessProblème NP-difficile
Complexity classClasse complexe
In computational complexity theory, a computational problem H is called NP-hard if, for every problem L which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from L to H. That is, assuming a…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.
