Het Handelsreizigersprobleem

Dr. ir. Jan Draisma
Universitair Hoofddocent Discrete en Toegepaste Algebraïsche Meetkunde
Technische Universiteit Eindhoven

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

Het zijn wiskundig verschrikkelijk spannende tijden. Van de zeven “Millenium Prize Problems”, waarmee zeven keer een miljoen dollar te verdienen is, is het afgelopen decennium al één opgelost: het Poincarévermoeden is bewezen door de Russische wiskundige Perelman. Dus we hebben nog zo’n 99 decennia voor de overige zes! Op één daarvan kom ik zo dadelijk terug. Het opgelost worden van zulke vraagstukken behoort tot de allergrootste wiskundige doorbraken.

Niettemin werken maar weinig wiskundigen direct aan deze grote problemen. Een belangrijke reden daarvoor is dat je, naar een metafoor van de beroemde wiskundige Grothendieck, een wiskundige noot beter kunt openwéken dan openkráken. Wiskundigen laten zich bij het ontginnen van nieuw terrein leiden door hun gevoel voor schoonheid, en de kleine stapjes die ze daarbij zetten zijn als het verse water waarin de noot steeds weer gedrenkt wordt tot de schil er vanzelf af valt.

Een tweede reden is dat er gewoonweg zoveel méér nieuwe wiskunde te ontdekken is. Een belangrijke ontwikkeling in mijn eigen deelgebied is de wisselwerking tussen toepassingen en nieuwe, zuiver wiskundige theorie. Algebraïsche meetkunde, de afgelopen anderhalve eeuw één van de zuiverste takken van de wiskunde, vindt de laatste jaren steeds vaker toepassingen, bijvoorbeeld in de biologie, de informatica, of in veilige elektronische communicatie. Daarover zo dadelijk nog iets meer. Voor de ontwikkeling van mijn vak is echter het verkeer in de omgekeerde richting minstens zo belangrijk: toepassingen leiden tot verrassende algebraïsche en meetkundige vraagstukken, waar nieuwe wiskundige theorie voor nodig is. In zijn voordracht “Can biology lead to new theorems?” beantwoordde wiskundige Sturmfels de titelvraag dan ook met een hartgrondig “Ja!”

2. Op welke wetenschappelijke doorbraak hoopt u?

Eén van de zes overgebleven Millenium Prize Problems is de vraag of “P gelijk is aan NP”. Deze vraag is het makkelijkst uit te leggen aan de hand van logistieke vraagstukken: dat een TomTom razendsnel de kortste route van A naar B kan berekenen komt omdat dit kortste-padprobleem in de klasse P zit; de Nederlandse informaticus Dijkstra bedacht daarvoor al in de jaren 50 een efficiënte rekenmethode. Maar voor het berekenen van een kortste handelsreiziger-route die een paar duizend voorgeschreven steden aandoet kennen we vooralsnog géén efficiënte rekenmethode. Sterker nog, waarschijnlijk bestaat zo’n methode helemaal niet! Dat probleem zit wel in de klasse NP, maar waarschijnlijk niet in P. Aantonen dat zo’n rekenmethode niet bestaat is een heilige graal van de theoretische informatica.

Het prachtige van wiskunde is dat een probleem op zoveel verschillende manieren bestudeerd kan worden. Zo is “P versus NP” de afgelopen jaren geherformuleerd tot een vraag in de algebraïsche meetkunde, die op het eerste gezicht helemaal niets met handelsreizigers of TomToms van doen heeft. Het zou geweldig zijn als deze “P versus NP meetkunde” tot een doorbraak gaat leiden! Maar ook als dat niet het geval is, dan levert ze heel boeiende nieuwe wiskunde op.

(Overigens, onder het motto “beter weken dan kraken” raakt mijn eigen onderzoek weliswaar aan die “P versus NP meetkunde”, maar zijn de onderzoeksvragen een stuk bescheidener.)

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

Het is onbegonnen werk om alle manieren op te sommen waarop de wiskunde als geheel bijdraagt aan de samenleving. Denk bijvoorbeeld aan het internet. De veiligheid van internetbankieren wordt met slimme toepassingen van getaltheorie gegarandeerd. Google maakt gebruik van geavanceerde lineaire algebra om bij gegeven zoektermen razendsnel de meest relevante pagina’s te vinden; dat zijn die met de hoogste “PageRank”. En, om bij zoekmachines te blijven, zogenaamde “deep belief networks” zijn wiskundige “machines” die kunnen “leren”. Als u in Google een typefout maakt, komt zo’n machine in actie en genereert de vraag “Did you mean….?”.

Mijn Amerikaanse collega Matthew Baker grapte ooit dat hij met terugwerkende kracht recht had op een deel van Google Inc., want “I taught Sergey Brin the Perron-Frobenius Theorem”. Dat is een wiskundige stelling waarop Google’s PageRank gebaseerd is. Zoals dat meestal gaat, bestond die stelling al lang vóór de toepassing gevonden werd, namelijk sinds 1907.

Omgekeerd wordt, zoals gezegd, veel mooie wiskunde geïnspireerd door toepassingen—ook deep belief networks leiden tot boeiende algebraïsch-meetkundige vragen. De weg van toepassing naar wiskunde én terug duurt meestal langer dan beleidsmakers lief is. Niettemin zijn óók toepassingen op lange termijn het meest gebaat bij puur “curiosity-driven” onderzoek enerzijds, en vrijblijvende brainstormsessies tussen wiskundigen en toepassers anderzijds.


Andere bijdragen in Wiskunde, Wiskundige problemen