Het ontwarren van knopen is zojuist een stukje eenvoudiger geworden. Een van de grootste uitdagingen in het wiskundig onderzoek naar knopen is het herkennen of iets een echte knoop is, of dat het een stuk touw is dat kan worden ontward tot een enkele lus. Een nieuw algoritme brengt dit raadsel veel sneller tot een ontknoping.
Wiskundig gezien is de definitie van een knoop een gesloten lijn – zoals een touw waarvan de uiteinden aaneen zijn gebonden – die niet ontward kan worden tot een enkele lus. Als de boel kan worden teruggebracht tot een lus, wordt het een ‘onknoop’ genoemd. ‘Net zoals nul geen positief getal is, is de onknoop geen echte knoop’, zegt fysicus Mark Dennis van de Universiteit van Birmingham in het Verenigd Koninkrijk.
Wiskundigen zoeken al zo’n honderd jaar naar een algoritme dat kan bepalen of een bepaalde knoop een echte knoop of een onknoop is. Nu heeft wiskundige Marc Lackenby aan de Universiteit van Oxford een algoritme bedacht dat hier veel sneller onderscheid tussen kan maken dan zijn voorgangers.
Complexe kruisingen
‘Het vinden van een onknoop lijkt heel intuïtief. Ons hele leven ontwarren we kabels, draden en snoeren van koptelefoons en zo. Maar het blijkt dat het wiskundig gezien veel abstracte vakgebieden raakt, die te maken hebben met geometrie in hoger-dimensionale ruimten’, zegt Dennis. ‘Er zijn diagrammen van knopen die je eerst ingewikkelder moet maken, voordat je ze kunt vereenvoudigen.’ Computers zijn niet goed in het herkennen wanneer ze op die strategie moeten overstappen.
De complexiteit van een knoop wordt bepaald door het aantal kruisingen dat hij bevat. Een kruising is de plek waar een deel van de lijn over of onder een ander deel doorgaat. Elke kluwen die zo kan worden verschoven dat hij geen kruisingen meer heeft, is een onknoop.
‘Je verwacht misschien dat het geen moeilijk probleem is. Maar als je begint na te denken over hoe een computer eigenlijk over zo’n vraag moet aanvliegen, realiseer je je dat je niet eens de juiste gereedschappen hebt om tot een beslissend antwoord te komen over de vraag of iets al dan niet een knoop is’, zegt Lackenby.
Tijdsbesparing
Andere wiskundigen hebben al eerder algoritmen bedacht die bepalen of een kluwen al dan niet geknoopt is. Het probleem met deze algoritmen is dat elke extra kruising in een knoop de benodigde tijd om tot een oordeel te komen verdubbelt.
Lackenby heeft nu het eerste algoritme bedacht dat die valkuil vermijdt. Aan de basis van zijn algoritme staat de truc om elke knoop te definiëren als de rand van een driedimensionale vorm.
Grensgeval
‘Je kunt je bijvoorbeeld een ronde knoop voorstellen die gewoon plat ligt – dat is dan de rand van een schijf’, zegt Lackenby. ‘Of je kunt je voorstellen dat je een strook papier neemt en de uiteinden aan elkaar vastmaakt, zodat het een lus vormt met wat kronkels erin. De rand van die strook papier zal dan een knoop zijn.’
Als de vorm die overeenkomt met de knoop kan worden vereenvoudigd tot een schijf, is de knoop eigenlijk een onknoop.
Bepalen of iets een onknoop is, heeft verreikende toepassingen: van bestuderen hoe DNA in cellen zit opgekruld tot het begrijpen van de plasmalussen op sterren. Een sneller algoritme is dus nuttig voor veel verschillende vakgebieden.
