NP-hårdhed
Et NP-hårdt problem er et ja/nej-problem, hvor det er mindst lige så svært at finde en løsning som at finde en løsning på det sværeste problem, hvis løsning hurtigt kan kontrolleres som værende sand. Nogle NP-hårde problemer er problemer, hvor en fungerende løsning hurtigt kan kontrolleres (NP-problemer), og andre er det ikke. NP-hårde problemer, som også er NP-problemer, hører til en kategori, der kaldes NP-komplet.
Et eksempel på et problem, der er mindst lige så svært at løse som ethvert andet problem, som vi hurtigt kan kontrollere løsninger på, og som også kan kontrolleres hurtigt (det er både NP-hårdt og NP):
En handelsrejsende sælger ønsker at besøge 100 byer i bil, idet han starter og slutter sin rejse hjemme. Han har en begrænset benzinbeholdning, så han kan kun køre i alt 10.000 km. Han vil gerne vide, om han kan besøge alle byerne uden at løbe tør for benzin.
Folk ved ikke, hvordan man løser dette problem hurtigere end ved at teste alle mulige svar, men hvis der findes en løsning, som gør det muligt for sælgeren at gøre dette, kan vi bruge en algoritme til at kontrollere, at det er sandt. Dette problem er også kendt som Travelling salesman problem.
Et eksempel på et problem, der er mindst lige så svært at løse som ethvert andet problem, som vi hurtigt kan kontrollere løsninger på, men som ikke kan kontrolleres hurtigt (det er NP-hårdt, men ikke NP):
hvis nogen starter et program, der bare går,
while(true){ continue; }og aldrig stopper den, vil den så køre for evigt?
Der er ingen kendt måde at finde en løsning på alle problemer af denne art på, og det kan heller ikke kontrolleres.
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.
