NP-hard

Categoria di problemi almeno tanto difficili quanto i più ardui della classe NP, senza dover appartenere a NP stessi. Per essi non si conoscono algoritmi efficienti, e spesso ci si accontenta di soluzioni approssimate.