Mogelijke doorbraak in beroemd vraagstuk over grafen

Wie met wie seks heeft gehad op de studentenvereniging, het wegennet tussen Nederlandse steden, de getallen van één tot en met duizend met minstens één gezamenlijke deler. Het zijn allemaal voorbeelden van een graaf – een verzameling knooppunten met verbindingen ertussen. Het is berucht moeilijk om van twee grafen te bepalen of ze in wezen hetzelfde zijn. Laszlo Babai claimt nu dat hij daarvoor een algemene en efficiënte methode heeft gevonden.

13 november 2015

Het zoemde deze week rond in wiskundeblogs en op het internet: er is een doorbraak in het berucht hardnekkige probleem om te bepalen of twee grafen isomorf zijn. Isomorf wil zoiets zeggen als: in wezen hetzelfde. Je kunt je makkelijk voorstellen, dat twee netwerken die er heel verschillend uitzien, eigenlijk precies dezelfde relaties tussen de knooppunten voorstellen. Dat geldt bijvoorbeeld voor deze twee simpele grafen:

Maar het zal duidelijk zijn, dat het voor grote grafen met veel verbindingen heel moeilijk is om te zien of ze al dan niet hetzelfde zijn. Grafen zijn er in allerlei soorten en maten, en voor diverse types bestaan al algoritmes (en dus computerprogramma’s) die in (bijna) alle gevallen efficiënt bepalen of twee grafen isomorf zijn. Maar er is nog geen algoritme dat dit gegarandeerd voor alle grafen presteert.

Vaststellen of twee grote grafen isomorf zijn, is van belang als je wilt checken of een gecompliceerd ontwerp voor een elektrisch circuit (bijvoorbeeld op een chip), na wijzigingen in het ontwerp om het compacter te maken, nog wel hetzelfde doet. Ook bij het bestuderen van grote moleculen, die uit veel atomen bestaan, wil je kunnen nagaan of twee verschillende ruimtelijke vormen van dat molecuul in wezen hetzelfde zijn, of toch net niet.

Sterk resultaat

De gerenommeerde, van origine Hongaarse wiskundige László Babai claimt nu dat hij zo’n algoritme heeft gevonden. Deze week hield hij er aan de Universiteit van Chicago (Verenigde Staten) al twee voordrachten over, en een derde staat gepland op 24 november. Website Science News citeert computerwetenschapper Jeremy Kun, die bij de eerste twee voordrachten aanwezig was: “Het grootste deel van het bewijs ziet eruit als heel, heel hard werk, en niet als een flits van inzicht.”

Hoewel het bewijs ongetwijfeld nog zal worden doorgeploegd door diverse collega’s van Babai, heeft Gerhard Woeginger, wiskundige aan de Technische Universiteit Eindhoven, er alle vertrouwen in. “Babai is in de zestig en heeft in zijn carrière al menig sterk resultaat bereikt. Hij is zo iemand die in dit stadium geen fouten maakt, hem vertrouw ik blindelings”, zegt hij.

Wiskundigen en computerwetenschappers zijn altijd op zoek naar algoritmes die efficiënt gecompliceerde rekenklussen oplossen. En ‘efficiënt’ betekent in dit verband, dat de benodigde computertijd ‘polynomiaal’ toeneemt met de grootte van de klus (zie het kader hieronder). Als het algoritme niet efficiënt werkt, maar iets doet wat eigenlijk neerkomt op domweg alle mogelijkheden uitproberen, neemt de computertijd exponentieel toe.

Cryptografie

“Dit is de grootste doorbraak op dit gebied in tien jaar,” stelt Woeginger onomwonden. “Maar er is nog heel wat werk te doen.” Babai’s claim is namelijk dat hij een quasi-polynomiaal algoritme gevonden heeft, dat qua groei van de rekentijd tussen polynomiaal en exponentieel in zit.

Zodra voor een bepaald probleem een polynomiaal algoritme gevonden is, is het eigenlijk ‘gekraakt’; het is geen uitdaging meer voor computerwetenschappers. Moderne geheimschriften en cryptografische technieken zijn gebaseerd op rekenklussen waarvoor alleen algoritmes met exponentiële rekentijd bekend zijn.

Dat geldt bijvoorbeeld voor het veel gebruikte RSA-geheimschrift. Dat is gebaseerd op de exponentiële rekentijd die nodig is om grote getallen in factoren te ontbinden. Cryptografen zijn daarom al gauw in rep en roer zodra in enig exponentieel rekenprobleem een doorbraak wordt bereikt. Volgens Woeginger is dat nu niet nodig. “Ik schat in dat dit resultaat niet toepasbaar is op andere moeilijke rekenklussen, zoals het in factoren ontbinden van grote getallen.”

Slimme en domme algoritmes

Wiskundigen hanteren een heel specifieke definitie van ‘efficiënt’ als het om algoritmes gaat. Toegespitst op het vergelijken van grafen: voor kleine exemplaren, met maar een handvol knooppunten, is er natuurlijk geen kunst aan om een programma te schrijven dat snel twee grafen vergelijkt. Waar het om gaat, is hoe de benodigde rekentijd groeit naarmate het aantal knooppunten N van de graaf toeneemt.

Bij een eenvoudig, ‘dom’ en inefficiënt programma neemt de rekentijd exponentieel toe: als het aantal knooppunten toeneemt van N naar N+1, verdubbelt de rekentijd T (in een formule: T ~ 2^N). Dat gaat heel hard: als het ‘domme’ programma er één seconde over doet om grafen met tien knooppunten te vergelijken, doet het al een kwartier over grafen met twintig knooppunten, twaalf dagen over types met dertig knooppunten, en 34 jaar over grafen met veertig knooppunten.

Als het programma ‘slim’ is, neemt T veel langzamer toe met N, namelijk als T ~N² of T~N³. In wiskundig jargon: T neemt polynomiaal toe met N. De rekentijd voor grafen met respectievelijk tien, twintig, dertig en veertig knooppunten is in het laatste geval slechts 1, 8, 27 en 64 seconden.

Bij de meeste rekenproblemen is de rekentijd T (afhankelijk van een of andere parameter N die de maat van het probleem aangeeft) ofwel exponentieel ofwel polynomiaal, en dit bepaalt of het algoritme ‘slim’ en efficiënt is of niet.

Het door Babai gevonden algoritme zit daar ergens tussen in: de rekentijd groeit iets harder dan polynomiaal, maar minder hard dan exponentieel. Het wordt daarom quasi-polynomiaal genoemd.

Reageer