Begreppen NP-hårdhet och NP-kompletthet handlar om hur svåra beslutproblem är att lösa och att kontrollera. Här följer en enkel, tydlig förklaring med exempel.
Vad betyder NP, NP-hårt och NP-komplett?
NP är klassen av ja/nej-problem där ett föreslaget svar (en kandidatlösning) kan kontrolleras snabbt — mer formellt: verifieras av en deterministisk algoritm i tidskomplexitet som är polynomisk i storleken på indata.
NP-hårt betyder att ett problem är minst lika svårt som de svåraste problemen i NP. Mer exakt: varje problem i NP kan omvandlas (reduceras) till det här problemet med en effektiv (polynomisk tid) omvandling. NP-hårda problem behöver inte själva ligga i NP — de kan vara svårare eller till och med olösbara.
NP-komplett betyder att problemet både är i NP och är NP-hårt. Dessa problem är de "svåraste" inom NP: om någon hittar en snabb (polynomisk) algoritm för ett NP-komplett problem så får man en snabb algoritm för alla problem i NP.
Viktig distinktion: lösa vs verifiera
Att lösa ett problem betyder att man hittar ett korrekt svar. Att verifiera betyder att man, givet ett förslag till svar, snabbt kan kontrollera att det verkligen är korrekt. Ett problem kan vara svårt att lösa men lätt att verifiera — det är typiskt för NP-problem.
Exempel 1 — NP-komplett (både NP-hårt och i NP)
Problembeskrivning: En resande försäljare vill köra bil och besöka 100 städer, börja och sluta hemma. Han har totalt högst 10 000 kilometer bensin till sitt förfogande. Frågan (i beslutform) är: finns det en rundtur som besöker alla städer och har total längd ≤ 10 000 km?
Detta är ett exempel på ett beslut som hör till Travelling Salesman Problem i beslutform. Om någon ger oss en specifik tur (en ordning på städerna) kan vi kontrollera snabbt att den verkligen besöker alla städer och att summan av sträckorna är ≤ 10 000 km — därför ligger detta beslutproblem i NP. Samtidigt är problemet minst lika svårt som de svåraste problemen i NP (det är NP-hårt), så sammanfogat är det ett klassiskt exempel på ett NP-komplett problem. Se också Travelling salesman problem.
Exempel 2 — NP-hårt men inte i NP (olösbart/osektbart)
Problembeskrivning (relaterat till stoppbarhet): Tänk dig ett program som körs i en oändlig slinga, till exempel:
while(true){ continue; }Frågan: kommer programmet att köra för evigt (stoppa aldrig)? Detta hör till det klassiska halting‑problemet. Halting‑problemet är olösbart (det finns inget algoritmiskt sätt som alltid bestämmer detta för alla program). Eftersom det är ännu svårare än de problem som ligger i NP kan sådana problem ses som NP-hårda — de är minst lika svåra som alla NP-problem — men de ligger inte i NP eftersom de inte kan verifieras eller beslutas med någon effektiv algoritm.
Med andra ord: för vissa NP-hårda problem kan man varken snabbt hitta en lösning generellt, eller snabbt kontrollera en kandidat (det finns helt enkelt inga algoritmer som alltid fungerar). För NP-kompletta problem kan man däremot i alla fall snabbt kontrollera en kandidatlösning — problemet är "bara" svårt att lösa snabbt, inte att verifiera.
Hur visar man att ett problem är NP-hårt?
- Man visar att varje problem i NP kan omvandlas till det aktuella problemet med en polynomisk transformation (en reducering).
- I praktiken brukar man reducera ett känt NP-hårt eller NP-komplett problem till det nya problemet för att visa svårigheten.
Sammanfattning
- NP: problem där ett förslag till lösning kan kontrolleras snabbt.
- NP-hårt: minst lika svårt som de svåraste problemen i NP; kan vara ännu svårare eller olösbart.
- NP-komplett: både i NP och NP-hårt — de svåraste problemen inom NP.
Exemplet med säljaren (TSP i beslutform) visar ett problem som är både NP-hårt och i NP (NP-komplett). Halting‑problemet är ett exempel på ett problem som kan betraktas som NP-hårt men som inte ligger i NP eftersom det är olösbart och inte går att verifiera med en effektiv algoritm.