Et NP-hårdt problem er et ja/nej-problem (en beslutningsproblematik), som er mindst lige så svært som ethvert problem i klassen NP. Formelt betyder det, at for hvert problem A i NP findes der en polynomiel-tids beregnbar funktion f (en såkaldt many-one-reduktion), sådan at et input x er et "ja"-tilfælde for A netop når f(x) er et "ja"-tilfælde for det NP-hårde problem. NP-hårdhed siger altså noget om relativ sværhedsgrad: alle problemer i NP kan oversættes effektivt til det NP-hårde problem.

Klassen NP består af beslutningsproblemer, hvor en foreslået løsning (et bevis eller en "certificate") kan kontrolleres for korrekthed i polynomiel tid på en deterministisk Turing-maskine. Nogle NP-hårde problemer ligger også i NP — disse kaldes NP-komplet. Et NP-komplet problem er både i NP og NP-hårdt, altså et af de "sværeste" problemer i NP.

Eksempel: NP-komplet problem (NP-hårdt og i NP)

Eksempel: En handelsrejsende ønsker at besøge 100 byer og starte og slutte hjemme. Han kan højst køre 10.000 km i alt. Spørgsmålet er: findes der en rute, som besøger alle byerne og har samlet længde ≤ 10.000 km?

Dette er en beslutningsvariant af Travelling salesman problem. Hvis man får en konkret rute (en permutation af byerne), kan man på ganske få trin beregne rutens samlede længde og dermed bekræfte, om den opfylder grænsen på 10.000 km — kontrol sker i polynomiel tid. Derfor ligger denne beslutningsvariant i NP. Man kender ingen generel metode til at finde en sådan rute hurtigere end ved at afprøve mange muligheder, og derfor betragtes problemet som NP-hårdt; kombinationen gør det NP-komplett. Hvis nogen fandt en polynomiel algoritme til at løse et NP-komplet problem, ville den give polynomielle løsninger til alle problemer i NP.

I teksten ovenfor nævnes også en algoritme til at kontrollere en foreslået løsning: vi kan hurtigt (i polynomiel tid) se, om en given rute opfylder længdebegrænsningen.

Eksempel: NP-hårdt men ikke i NP (typisk: uafgørligt)

Eksempel: Overvej spørgsmålet: "Givet et vilkårligt program, vil det køre for evigt på en bestemt input?" Som konkret lille program kan man se på:

while(true){ continue; }

Dette enkle program kører naturligvis for evigt, men spørgsmålet i sin generelle form — halting-problemet: "Stopper et givet program på et givet input?" — er uafgørligt (undecidable). Der eksisterer ikke nogen algoritme, som for alle program-input-par kan afgøre dette korrekt. Sådanne problemer kan ikke ligge i NP (NP består af besluttelige problemer), men de kan være NP-hårde i den forstand, at alle NP-problemer kan reduceres til dem. Halting-problemet er et klassisk eksempel på et problem, som er sværere end alle problemer i NP og samtidig uden nogen effektiv verifikationsprocedure for alle instanser.

Hvad betyder det i praksis?

  • Hvis et problem er NP-komplett, betyder det, at det er usandsynligt, at der findes en polynomiel tidsalgoritme til at løse alle instanser — men det er ikke bevist. Det er tæt knyttet til det berømte åbne problem P vs NP.
  • NP-hårde problemer, som ikke ligger i NP (fx uafgørlige problemer), er endnu værre: de kan ikke engang altid verificeres korrekt i polynomiel tid, og nogle er slet ikke besluttelige.
  • I praksis bruger man ofte heuristikker, approximation eller specialtilfælde (fx metoder, der virker godt for små eller specielle instanser), fordi man som regel ikke kan løse vilkårlige NP-komplette instanser effektivt i alle tilfælde.

Sammenfattende: NP-hårdhed handler om relativ sværhedsgrad via polynomiel reduktion; NP-komplet betyder både NP-hårdt og i NP (altså verificerbart hurtigt). Uafgørlige problemer som halting ligger uden for NP, men kan stadig være "mindst lige så svære" som alle NP-problemer, hvilket gør dem NP-hårde i den brede forstand.