Waar ligt de grens tussen het berekenbare en het onberekenbare?

Voor de wiskunde en de informatica is het een open vraag of alle grootschalige rekenproblemen uiteindelijk zijn op te lossen met brute rekenkracht. Wiskundigen vermoeden dat sommige complexe rekenproblemen de macht van de computer fundamenteel te boven gaan. Maar zolang niemand dat heeft bewezen, leeft de hoop dat het schijnbaar onoplosbare toch oplosbaar zal blijken te zijn.

Voor het vinden van de kortste route tussen twee punten op een wegenkaart bestaat een snelle rekenkundige oplosmethode, die we danken aan de in 2002 overleden Nederlandse informaticus Edsger Dijkstra. De navigatie-apparatuur in onze auto gebruikt die methode om ons snel van het ene naar het andere punt te gidsen.

Bruno Mallart© Bruno Mallart

Complexe rekenproblemen waarvoor een snelle oplossingsmethode bestaat, noemen wiskundigen ‘P-problemen’. Helaas zit de wereld vol met rekenproblemen waarvoor zo’n snelle oplosmethode nog niet is gevonden. Zij worden ‘NP-volledige problemen’ genoemd.

Voorbeelden zijn het ontwerpen van schoolroosters en dienstregelingen, het routeren van transportmiddelen, het bepalen van de beste locaties voor distributiepunten en het voorspellen van de driedimensionale structuur van biologische eiwitten.

Voor NP-volledige problemen is weliswaar geen snelle oplosmethode voorhanden, maar als op de een of andere manier toch een oplossing is gevonden, kunnen we die vaak wel snel verifiëren. Zo hebben we geen snelle methode om de priemfactoren van het getal 4.294.967.297 te vinden, maar kunnen we wel eenvoudig verifiëren dat 641 en 6.700.417 geldige priemfactoren zijn (immers: 641 × 6.700.417 = 4.294.967.297).

Dit ‘eenrichtingsverkeer’ van NP-volledige problemen gebruiken banken om digitale transacties te beveiligen.

Als voor één NP-volledig probleem een snelle oplosmethode wordt gevonden, dan zijn ook alle andere NP-volledige problemen snel oplosbaar. Omgekeerd geldt hetzelfde: als een NP-volledig probleem géén snelle oplosmethode heeft, dan is dat ook zo voor alle andere NP-volledige problemen. Schijnbaar ‘onoplosbare’ NP-volledige problemen zijn onderwerp van veel onderzoek.

Rekentijd

Voor NP-volledige problemen geldt dat de rekentijd vooralsnog exponentieel toeneemt met de grootte van het probleem. Ook niet al te grote, in de praktijk voorkomende NP-volledige problemen zijn op dit moment onoplosbaar, zelfs al zouden alle computers ter wereld er miljoenen jaren op ploeteren. In de praktijk creëren wiskundigen dus methoden om de uitkomst te benaderen zonder dat de rekentijd uit de hand loopt. Nederlandse wiskundigen ontwikkelden zo bijvoorbeeld de methode waarmee de Nederlandse Spoorwegen in 2007 een nieuwe treindienstregeling ontwierpen.

De fundamentele wiskundige vraag is echter of NP-volledige problemen misschien zijn te vereenvoudigen tot P-problemen. Die vraag is ook van groot praktisch belang. Als NP-volledige problemen op de een of andere manier zouden zijn te vereenvoudigen tot P-problemen, dan zou dat betekenen dat we ook snelle oplosmethoden kunnen vinden voor problemen die nu nog te lastig zijn. Als echter bewezen kan worden dat NP-volledige problemen fundamenteel verschillen van P-problemen, dan geeft dat nieuw inzicht in de oorzaak van de complexiteit van problemen.

De vraag ‘NP = P?’ is dan ook een van zeven Millennium Prize Problems: belangrijke, klassieke, onopgeloste wiskundige vragen die in 2000 werden geselecteerd door het Clay Mathematics Institute in Cambridge, Massachusetts. Voor de oplossing ervan werd één miljoen dollar uitgeloofd.