OKC_Logo

Is P hetzelfde als NP?

Mathematics

Wilt u een miljoen dollar winnen? Daarvoor hoeft u maar één vraag te beantwoorden bij het Amerikaanse Clay Mathematics Insitute: Is P hetzelfde als NP? In deze blogpost nemen we u mee in onze wereld. We gaan we in op deze vraag en de consequenties die deze vraag heeft voor het ontwerpen en ontwikkelen van algoritmes.

Waarom is deze vraag interessant?

Wie onze eerdere blogposts heeft gelezen, heeft gelezen over ‘heuristieken’: Snelle oplosmethoden voor lastige problemen die niet gegarandeerd de allerbeste oplossing bieden, maar die toch gebruikt worden omdat het te lang kan duren om de optimale oplossing wel te vinden.

Problemen in P zijn de makkelijke problemen. Hiervoor kunnen we snel de ideale oplossing bepalen. Problemen in NP zijn lastig. Hiervoor kennen we geen snel algoritme om de optimale oplossing te vinden en daarom moeten we een keuze maken: Gaan we voor de allerbeste oplossing en mag dat veel tijd kosten, of moeten we snel een acceptabele oplossing vinden?

Juist in dat tweede geval kiezen we voor heuristieken. Die worden bijvoorbeeld gebruikt in de navigatie in uw auto, want niemand wil vier dagen wachten op de allersnelste route van Amsterdam naar Maastricht als we binnen een minuut een goede route kunnen bepalen, die misschien een halve kilometer en 10 seconden langer is. Dit gaat echter niet op voor alle ‘moeilijke’ problemen. Als er een nieuwe dienstregeling moet komen voor het openbaar vervoer in uw woonplaats (denk aan de verbindingen tussen bussen, trams, metro’s, etc.), dan willen we zo veel mogelijk overstappen die goed op elkaar aansluiten. Het is niet erg als het een paar dagen langer duurt om de optimale dienstregeling te bepalen als dat in de toekomst dagelijks duizenden mensen aan een goede overstap helpt.

Het is een uitdaging om de balans te vinden tussen de efficiëntie van planningen en de tijd die het kost om tot zo’n planning te komen. Het Clay Mathematics Institute vraagt eigenlijk om aan te tonen dat elk probleem dat we nu als ‘moeilijk’ beschouwen op een ‘makkelijke’ manier exact kan worden opgelost, of om te bewijzen dat dat niet kan. Sinds het begin van dit millennium heeft nog niemand het antwoord gevonden op deze vraag, ondanks het prijzengeld en de relevantie van dit probleem voor onderzoek naar (onder andere) algoritmes, artificiële intelligentie, wiskunde en filosofie.

Voorlopig zullen we het dus moeten doen met algoritmes die op maat worden gemaakt voor elk ‘moeilijk’ probleem. Wij kunnen met u meedenken om een algoritme voor u te ontwerpen en te ontwikkelen!  Neem contact met ons op voor een algoritme dat voor u op maat is gemaakt!