Wiskunde vraagstukken en praktische toepassingen

Prof.dr. Lex Schrijver
Onderzoeker Discrete Wiskunde en Optimalisering
Centrum Wiskunde & Informatica en Universiteit van Amsterdam

1. Wat is de belangrijkste wetenschappelijke ontwikkeling in uw vakgebied?

Een van de belangrijkste ontdekkingen van de laatste jaren op mijn vakgebied is gedaan door Paul Seymour in Princeton in samenwerking met collega’s elders. Deze ontdekking geeft inzicht in de structuur van netwerken, zoals transport-, energie- en communicatienetwerken, waaronder het internet.

Ruwweg gezegd bleek dat elk netwerk gedecomponeerd kan worden in kleinere netwerken, tenzij in het netwerk een welomschreven, lastig kern-netwerk voorkomt. Deze ‘graaf minor stelling’ maakt het mogelijk netwerkproblemen aan te pakken door ze te reduceren tot kleinere problemen dan wel je te richten op zo’n lastige kern in het netwerk.

Om de stelling precies te beschrijven is enig niet al te diep wiskundig formalisme nodig, maar het bewijs vergde meer dan twintig artikelen, verschillende van zo’n 50 pagina’s. De stelling heeft geleid tot een stroom vervolgonderzoek waarin belangrijke gevolgen van de graaf minor stelling werden afgeleid die kunnen worden toegepast op bijvoorbeeld het snel bepalen van de optimale verbindingen op een computerchip en op het kleuren van grafen, hetgeen van belang is voor het optimaliseren van schoolroosters en dienstregelingen.

Een andere, misschien wat makkelijker uit te leggen recente doorbraak is het bewijs van een vermoeden dat de astronoom Kepler in 1611 publiceerde. Het betreft het optimale stapelen van bollen, bijvoorbeeld sinaasappels. Als men zoveel mogelijk sinaasappels in een container wil stoppen, lijkt de volgende aanpak de beste. Leg een eerste laag sinaasappels neer in een hexagonaal patroon (dus elke sinaasappel raakt zes andere). Leg elke volgende laag sinaasappels in de laagste punten boven de vorige laag. Kepler vermoedde dat op deze manier (zoals ook de groenteman het meestal doet) inderdaad zoveel mogelijk sinaasappels in de container gaan.

Ondanks de aannemelijkheid van dit vermoeden, was men bijna vier eeuwen niet in staat ook werkelijk te bewijzen dat deze stapeling inderdaad optimaal is. Eind 20ste eeuw vond uiteindelijk Thomas Hales een bewijs, gebaseerd op lineaire programmering en veel computerhulp. Net als bij veel andere problemen is hierbij niet zozeer het resultaat van belang, maar vooral ook de gevonden methode die toepasbaar bleek op veel andere problemen die vragen om een optimale stapeling van objecten.

2. Op welke wetenschappelijke doorbraak hoopt u?

Ik hoop op de oplossing van het vraagstuk dat gewoonlijk met “NP=P?” wordt aangeduid. Voor de betekenis van dit acroniem is weer wat wiskundig formalisme nodig, maar het probleem kan ook worden beschreven met de vraag: Bestaan er snelle algoritmen (computerprogramma’s) voor het op-

lossen van ‘combinatorische’ problemen als het maken van schoolroosters en dienstregelingen, het optimaal routeren van bestelwagens langs afleveradressen, het bepalen van de beste locaties voor fabrieken en distributiepunten, en het voorspellen van de driedimensionale structuur van proteïnen?

Een algoritme wordt snel genoemd als de rekentijd niet exponentieel groeit met de grootte van het probleem, maar slechts polynomiaal. Voor de genoemde praktische problemen is zo’n snelle methode niet bekend en ze blijken erg lastig op te lossen, maar men heeft kunnen bewijzen dat ze alle even lastig zijn: Als voor één van de problemen een snelle methode wordt gevonden, kan daaruit een snelle methode voor elk van de andere problemen worden afgeleid!

De lijst kan worden uitgebreid met honderden andere praktische problemen, en er zit een equivalent universeel probleem achter. Daardoor is zowel een positief als een negatief antwoord op de vraag van groot belang. Een positief antwoord geeft verrassend snelle methoden om veel van de nu nog

te lastige praktische problemen op te lossen. Een negatief antwoord op de vraag levert een fundamenteel nieuw inzicht in de oorzaak van de lastigheid van de problemen, en geeft aldus een mogelijkheid de kern van de complexiteit te lokaliseren en aan te pakken. Bovendien blijkt een antwoord ook van groot belang voor de veiligheid van het verzenden van gecodeerde informatie bijvoorbeeld over het internet.

De vraag “NP=P?” werd voor het eerst expliciet gesteld rond 1970, maar wortelt in eerder werk van o.a. Turing, von Neumann en Gödel. Het belang wordt onderstreept door het feit dat het “NP=P?” probleem op de lijst van de belangrijkste zeven wiskundige problemen voor de 21ste eeuw van het Clay Mathematics Institute staat (The Millennium Prize Problems). Voor de oplossing van elk van deze problemen is een prijs van 1 miljoen dollar uitgeloofd.

3. Wat is de waarde van uw vakgebied voor de samenleving?

Deze waarde moge blijken uit de bovengenoemde praktische toepassingen.


Andere bijdragen in Wiskunde, Wiskundige problemen