Wiskundigen vieren 'simpele' oplossing breinbreker

thinkstock
Zelf heeft de Hongaars-Amerikaanse wiskundige Lásló Babai (65) het nog over een voorlopig resultaat, waarin zijn collega's gaten mogen schieten. Graag zelfs. Maar twee voordrachten verder, gewoon met een krijtje op een schoolbord, noemen wiskundigen zijn nieuwe analysetheorie voor netwerken nu al de belangrijkste doorbraak van de laatste tien jaar.

"Dit it is een gigantische stap", zegt wiskundige en informaticus Gerhard Woeginger (TU Eindhoven), zelf een specialist in de netwerktheorie die Babai specifiek behandelt. "Hij biedt nieuwe inzichten waarop we lang hebben moeten wachten."

Wat Babai, verbonden aan de Universiteit van Chicago, in feite laat zien is dat er een relatief eenvoudige oplossing bestaat voor wat werd gezien als een onmogelijke wiskundige breinbreker.

Ook de Amsterdamse Spinozaprijswinnaar Lex Schrijver (Centrum voor Wiskunde en Informatica), ooit de man achter het spoorboekje van de NS, noemt het nieuwe werk opmerkelijk. 'Dit is een behoorlijke doorbraak, het gaat in de richting van een Millenniumprijs', reageert hij. Het Amerikaanse Clay instituut loofde in 2000 een miljoen dollar elk uit voor de oplossingen van zeven fundamentele wiskundige raadsels. De vraag of sommige vraagstukken echt oneindig veel moeilijker zijn dan andere, was er daar één van.

Babai concentreert zich in zijn onderzoek op het vergelijken van zogeheten grafen: mathematische netwerken van knooppunten en verbindingen. Een belangrijke vraag daarbij is of twee gegeven netwerken wellicht verschillende weergaven van hetzelfde ding zijn.

Babai laat zien dat er een relatief eenvoudige oplossing bestaat voor wat werd gezien als een onmogelijke wiskundige breinbreker

Rekenstappen

Voor kleine netwerken is dat nog met hoofd en hand te doen. Maar voor grotere netwerken niet, en de vraag is hoeveel meer rekenstappen er nodig zijn om het antwoord te vinden voor een groter netwerk. Wiskundig gelden vraagstukken die groeien als een macht (bijvoorbeeld een kwadraat) van het aantal knooppunten als snel oplosbaar. Die familie problemen noemen wiskundigen P.

Vrijwel onoplosbaar zijn zogeheten NP-complete problemen, waarvan het rekenwerk meteen 2 tot de macht tien of nog meer groeit als het aantal knooppunten tienmaal zo groot is.

"Dit zogeheten grafen isomorfisme is een van de weinige vraagstukken waarvan we niet goed wisten of het rekenwerk snel te doen is, of exponentieel uit de hand loopt. Babai zegt te kunnen aantonen dat het dicht bij het eerste zit: snel oplosbaar." Interessant, zegt Schrijver, is dat dat kan betekenen dat P en NP niet twee gescheiden mathematische werelden zijn, maar toch één.

Onberekenbaar probleem

Dat is vooral belangrijk, zegt in Eindhoven Gerhard Woeginger, omdat een ander berucht onberekenbaar probleem een hoofdrol speelt in moderne cryptografie: het uiteenrafelen van grote getallen in priemgetallen. "Als dat niet principieel onbegonnen werk is, hebben we uiteindelijk misschien zelfs een veiligheidsprobleem", zegt hij.

Voorlopig heeft Babais werk echter niet heel veel gevolgen, denkt Woeginger, die de serie voordrachten van zijn collega sinds de eerste, vorige week dinsdag, online volgt. Voor netwerk-analyses bestaan inmiddels allerlei benaderende computertechnieken, die prima werken. En de Clay prijs van een miljoen ziet hij niet naar Babai gaan, hoezeer die hem ook gegund is. "Daarvoor is dit een te specifiek geval en geen algemene oplossing op de vraag of P hetzelfde is als NP of niet. In feite gaat de vraag ons al veertig jaar echt boven de pet. Niks werkt en de ideeën zijn een beetje op."

'Niks werkt en de ideeën zijn een beetje op'

Gerhard Woeginger, wiskundige en informaticus (TU Eindhoven)
De Volkskrant / Wikimedia