Problem NP-trudny (NPH, ) – problem obliczeniowy, którego rozwiązanie jest co najmniej tak trudne, jak rozwiązanie każdego problemu z klasy NP.
Formalna definicja problemu NP-trudnego jest następująca: Problem jest NP-trudny, jeżeli pewien problem NP-zupełny jest do niego redukowalny wielomianową transformacją Turinga.
Innymi słowy, problem NP-zupełny można rozwiązać w wielomianowym czasie algorytmem rozwiązującym problem NP-trudny przez wykorzystanie hipotetycznej procedury sprowadzającej problem NP-zupełny do problemu NP-trudnego jeżeli tylko daje się wykonać w wielomianowym czasie. NP-trudność można zdefiniować także w kategorii języków formalnych (a nie problemów). Do klasy problemów NP-trudnych mogą należeć problemy różnego typu: decyzyjne, przeszukiwania, optymalizacyjne.