NP-hard

NP-difícil (NP-hard) refere-se a uma classe de problemas que são, informalmente, 'pelo menos tão difíceis quanto os problemas mais difíceis em NP'. Um problema é NP-difícil se um algoritmo para resolvê-lo em tempo polinomial puder ser usado para resolver todos os problemas em NP em tempo polinomial.