NP-hårdhet
Ett NP-hårt problem är ett ja/nej-problem där det är minst lika svårt att hitta en lösning som att hitta en lösning på det svåraste problemet vars lösning snabbt kan kontrolleras som sann. Vissa NP-hårda problem är sådana där en fungerande lösning snabbt kan kontrolleras (NP-problem) och andra är det inte. NP-hårda problem som också är NP-problem passar in i en kategori som kallas NP-komplett.
Ett exempel på ett problem som är minst lika svårt att lösa som alla andra problem som vi snabbt kan kontrollera lösningar för, och som också är snabbt kontrollerbart (det är både NP-hårt och NP):
En resande försäljare vill besöka 100 städer med bil och börja och sluta sin resa hemma. Han har en begränsad mängd bensin, så han kan bara köra totalt 10 000 kilometer. Han vill veta om han kan besöka alla städer utan att bensinen tar slut.
Vi vet inte hur vi ska lösa detta problem snabbare än att testa alla möjliga svar, men om vi hittar en lösning som gör det möjligt för säljaren att göra detta kan vi använda en algoritm för att kontrollera att det är sant. Detta problem är också känt som Travelling salesman problem.
Ett exempel på ett problem som är minst lika svårt att lösa som alla andra problem som vi snabbt kan kontrollera lösningar för, men som inte kan kontrolleras snabbt (det är NP-hårt, men inte NP):
Om någon startar ett program som helt enkelt går,
while(true){ continue; }och aldrig stoppar den, kommer den att gå för evigt?
Det finns inget känt sätt att hitta en lösning på alla problem av det här slaget, och det går inte heller att kontrollera.
Frågor och svar
F: Vad är ett NP-hårt problem?
S: Ett NP-hårt problem är en typ av matematiskt problem som används inom datavetenskapen och som är ett ja/nej-problem där det är minst lika svårt att hitta en lösning som det svåraste problemet vars lösning snabbt kan kontrolleras som sann.
F: Kan en fungerande lösning snabbt kontrolleras för alla NP-hårda problem?
S: Nej, endast vissa NP-hårda problem, så kallade NP-problem, har lösningar som snabbt kan kontrolleras.
F: Vad kallas kategorin för NP-hårda problem som också är NP-problem?
S: NP-hårda problem som också är NP-problem passar in i en kategori som kallas NP-kompletta.
F: Är alla NP-hårda problem NP-kompletta?
S: Nej, inte alla NP-hårda problem är NP-kompletta. Endast de som också är NP-problem faller inom denna kategori.
F: Är NP-hårda problem lätta att lösa?
S: Nej, NP-hårda problem är inte lätta att lösa. Faktum är att det är minst lika svårt att hitta en lösning på dem som att hitta en lösning på det svåraste problem vars lösning snabbt kan kontrolleras som sann.
F: Finns det några fördelar med att lösa NP-hårda problem?
S: Ja, att lösa NP-hårda problem kan ge fördelar inom olika områden, t.ex. datavetenskap, fysik och samhällsvetenskap, eftersom de kan kräva komplexa beräkningar och modellering.
F: Finns det pågående forskning om hur man löser NP-hårda problem?
S: Ja, forskning om att lösa NP-hårda problem pågår eftersom dessa problem fortsätter att vara relevanta inom olika områden, och att hitta effektiva algoritmer och lösningar kan ha betydande konsekvenser.
