Promotie Uitgelicht: Bruno Loff
Op 21 januari promoveert Bruno Loff (1984) aan de UvA. Tijdens zijn promotieonderzoek aan het Institute for Language, Logic and Computation (ILLC) lichtte hij een tipje van de sluier op van het zogeheten knapzakprobleem.
Wat heb je gedaan?
‘Ik heb gezocht naar nieuwe algoritmen. Een algoritme is een recept voor de oplossing van een wiskundig probleem. Wiskundigen zijn altijd op zoek naar het efficiëntste algoritme. Een inefficiënt algoritme kost een computer enorm veel tijd en geheugen. Ik heb onder meer gezocht naar betere algoritmen voor het zogeheten knapzakprobleem.
Dit probleem gaat uit van een kamer met items met een bepaald gewicht en een tas met een bepaalde capaciteit. Je moet zo veel mogelijk gewicht in de tas zien te krijgen. Je kunt de items van groot naar klein in de tas stoppen tot het niet meer kan. Maar deze strategie mislukt als je bijvoorbeeld een item van driekwart van de totale capaciteit hebt en twee items van de halve capaciteit. Dan stop je al als de tas voor driekwart vol is. Complexiteitstheoretici denken dat er geen efficiënt algoritme is dat dit knapzakprobleem kan oplossen. Ik heb bewezen dat er in een bepaald gebied in de wiskunde inderdaad geen efficiënt algoritme is vinden te voor dit probleem.’
Kun je dat uitleggen?
‘Stel je een groot vierkant voor waar alle efficiënte algoritmes in zitten. Wiskundigen denken dat geen enkel algoritme in dat grote vierkant het knapzakprobleem kan oplossen. Ik heb een klein vakje in dat grote vierkant uitgeplozen. Dit vakje bevat elk zogeheten ‘efficiënte semi-algebraïsch parallel algoritme’. Inderdaad bevindt zich daar geen algoritme dat het knapzakprobleem kan oplossen. Ik heb dit bewezen met behulp van de ‘prooftechnique’ van computerwetenschapper Ketan Mulmuley. Bewijzen dat het knapzakprobleem in het hele vierkant geen efficiënt algoritme heeft, is een nog veel ingewikkelder probleem, bekend als het ‘P versus NP probleem’. Dit wordt beschouwd als de heilige graal van mijn onderzoeksgebied.’
Je bent inmiddels teruggegaan naar je geboorteland Portugal, doe je daar vervolgonderzoek?
‘Nee, vanaf maart ga ik hier een half jaar mediteren in een huis midden in een bos. Tijdens mijn promotie ben ik met Vipassana-meditatie begonnen. Het heeft me veel gebracht. Ik heb vaak op het punt gestaan om met mijn promotieonderzoek te stoppen omdat ik me niet meer kon motiveren. Mede door te mediteren heb ik toch volgehouden. Mediteren geeft me stabiliteit en maakt me weer enthousiast. Ik heb ook veel steun gehad van mijn begeleider Harry Buhrman. Hij wist me als ik wilde stoppen steeds over te halen om door te gaan. Daar ben ik hem nu ontzettend dankbaar voor.’
Ga je na dat half jaar wel weer verder met onderzoek?
‘Ik twijfel nog. Dit vakgebied, de computationele complexiteitstheorie, is interessant, maar erg theoretisch. Ik weet bovendien niet of onderzoeker zijn voor mij de meest genereuze manier is om mijn vaardigheden te gebruiken. Misschien wel, misschien niet. Ik zou ook graag iets praktisch doen. Het komende half jaar zal ik gebruiken om te besluiten welke richting ik hierna op ga.’
Auteur: Carin Röst