Definition på NP-hårdhed: NP, NP-komplet og eksempler
Forstå NP-hårdhed, NP og NP-komplet med tydelige definitioner og konkrete eksempler som Travelling Salesman og halting-problemet.
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.
Spørgsmål og svar
Q: Hvad er et NP-hårdt problem?
A: Et NP-hårdt problem er en type matematisk problem, der bruges i datalogi, og som er et ja/nej-problem, hvor det at finde en løsning er mindst lige så svært som at finde en løsning til det sværeste problem, hvis løsning hurtigt kan kontrolleres som værende sand.
Q: Kan man hurtigt tjekke en fungerende løsning til alle NP-hårde problemer?
A: Nej, kun nogle NP-hårde problemer, kaldet NP-problemer, har løsninger, der kan tjekkes hurtigt.
Q: Hvad kaldes kategorien for NP-hårde problemer, der også er NP-problemer?
A: NP-hårde problemer, der også er NP-problemer, passer ind i en kategori, der hedder NP-komplet.
Q: Er alle NP-hårde problemer NP-komplette?
A: Nej, ikke alle NP-hårde problemer er NP-komplette. Kun dem, der også er NP-problemer, falder ind under denne kategori.
Spørgsmål: Er NP-hårde problemer nemme at løse?
A: Nej, NP-hårde problemer er ikke lette at løse. Faktisk er det mindst lige så svært at finde en løsning på dem som at finde en løsning på det sværeste problem, hvis løsning hurtigt kan tjekkes som værende sand.
Q: Er der nogen fordele ved at løse NP-hårde problemer?
A: Ja, løsning af NP-hårde problemer kan give fordele inden for forskellige områder, såsom datalogi, fysik og samfundsvidenskab, da de kan kræve komplekse beregninger og modellering.
Q: Er der igangværende forskning i løsning af NP-hårde problemer?
A: Ja, der forskes løbende i at løse NP-hårde problemer, da disse problemer fortsat er relevante inden for forskellige områder, og det kan have betydelige konsekvenser at finde effektive algoritmer og løsninger.
Søge