NP-difficile

NP-difficile, en théorie de la complexité de calcul, est la propriété définissant une classe de problèmes qui sont informellement « au moins aussi difficiles que les problèmes les plus difficiles dans NP ».

Un exemple simple de problème NP-difficile est le problème de la somme des sous-ensemble (d'une complexité algorithmique importante).

Une spécification plus précise est: un problème H est NP-difficile lorsque chaque problème L de NP peut être réduit en temps polynomial à H ; autrement dit, en supposant une solution de H a une unité de temps, M solution d » peut être utilisé pour résoudre L en temps polynomial.   En conséquence, trouver un algorithme polynomial pour résoudre tout problème de NP-difficile donnerait des algorithmes polynomiaux pour tous les problèmes de NP, ce qui est peu probable car beaucoup d'entre eux sont considérés comme difficiles.

Une idée fausse commune est que NP dans "NP-hard" signifie "non-polynomial" alors qu'en réalité, il signifie " problèmes polynomiaux acceptables non déterministes ".  On soupçonne qu'il n'existe pas d'algorithme ms polynomial pour les problèmes NP-difficiles, mais cela n'a pas été prouvé.  De plus, la classe P, dans laquelle tous les problèmes peuvent être résolus en temps polynomial, est contenue dans la classe NP