Een NP-hard probleem is een ja/nee probleem waarbij het vinden van een oplossing voor het probleem minstens zo moeilijk is als het vinden van een oplossing voor het moeilijkste probleem waarvan de oplossing snel kan worden gecontroleerd. Sommige NP-harde problemen zijn problemen waarbij een werkende oplossing snel kan worden gecontroleerd (NP-problemen) en andere niet. NP-harde problemen die ook NP-problemen zijn, passen in een categorie die NP-compleet wordt genoemd.
Een voorbeeld van een probleem dat minstens zo moeilijk op te lossen is als elk ander probleem waarvoor we snel oplossingen kunnen controleren, dat ook snel te controleren is (het is zowel NP-hard als NP):
Een reizende verkoper wil 100 steden bezoeken door thuis te rijden, te beginnen en te eindigen. Hij heeft een beperkte voorraad benzine, zodat hij in totaal maar 10.000 kilometer kan rijden. Hij wil weten of hij alle steden kan bezoeken zonder dat de benzine opraakt.
Mensen weten niet hoe ze dit probleem sneller kunnen oplossen dan door elk mogelijk antwoord te testen, maar als er een oplossing wordt gevonden die de verkoper in staat stelt dit te doen, kunnen we met behulp van een algoritme controleren of het waar is. Dit probleem wordt ook wel het Reizende Verkopersprobleem genoemd.
Een voorbeeld van een probleem dat minstens zo moeilijk op te lossen is als elk ander probleem waarvoor we snel oplossingen kunnen controleren, maar dat niet snel kan worden gecontroleerd (het is NP-hard, maar het is geen NP):
als iemand een programma start dat gewoon gaat,
terwijl (waar){ ga door; }
en stopt het nooit, zal het eeuwig blijven lopen?
Er is geen bekende manier om een oplossing te vinden voor dit soort problemen, en dit kan ook niet worden gecontroleerd.
Vragen en antwoorden
V: Wat is een NP-hard probleem?
A: Een NP-hard probleem is een type wiskundig probleem in de informatica dat een ja/nee probleem is waarbij het vinden van een oplossing minstens even moeilijk is als het vinden van een oplossing voor het moeilijkste probleem waarvan de oplossing snel als waar gecontroleerd kan worden.
V: Kan een werkende oplossing snel gecontroleerd worden voor alle NP-harde problemen?
A: Nee, alleen sommige NP-harde problemen, de zogenaamde NP-problemen, hebben oplossingen die snel gecontroleerd kunnen worden.
V: Hoe heet de categorie voor NP-harde problemen die ook NP-problemen zijn?
A: NP-harde problemen die ook NP-problemen zijn, passen in een categorie die NP-compleet wordt genoemd.
V: Zijn alle NP-harde problemen NP-compleet?
A: Nee, niet alle NP-harde problemen zijn NP-compleet. Alleen de problemen die ook NP-problemen zijn, vallen in deze categorie.
V: Zijn NP-harde problemen gemakkelijk op te lossen?
A: Nee, NP-harde problemen zijn niet gemakkelijk op te lossen. In feite is het vinden van een oplossing voor deze problemen minstens zo moeilijk als het vinden van een oplossing voor het moeilijkste probleem waarvan de oplossing snel als waar kan worden gecontroleerd.
V: Zijn er voordelen verbonden aan het oplossen van NP-harde problemen?
A: Ja, het oplossen van NP-harde problemen kan voordelen bieden op verschillende gebieden, zoals computerwetenschappen, natuurkunde en sociale wetenschappen, omdat ze complexe berekeningen en modellering kunnen vereisen.
V: Is er lopend onderzoek naar het oplossen van NP-harde problemen?
A: Ja, er wordt voortdurend onderzoek gedaan naar het oplossen van NP-harde problemen, omdat deze problemen op verschillende gebieden relevant blijven en het vinden van efficiënte algoritmen en oplossingen belangrijke implicaties kan hebben.
