Substructural logics and fast-growing complexities
Substructurele logica's en snelgroeiende complexiteiten
Vitor Rodrigues Greati onderzoekt hoe rekenkundig moeilijk het is om te redeneren binnen bepaalde niet-klassieke logische systemen, en ontwikkelt wiskundige hulpmiddelen om die moeilijkheidsgraad te meten.
Deel 1 richt zich op substructurele logica's, logische systemen die enkele gebruikelijke regels van de klassieke logica loslaten (zoals de mogelijkheid om informatie vrij te herschikken, te herhalen of te negeren). Dit maakt ze bruikbaar voor redeneren in situaties waarin volgorde en middelen ertoe doen, zoals computerprogramma's, fysische processen of natuurlijke taal. Of een bewering geldig is binnen deze logica's kan in theorie door een algoritme worden bepaald, maar niet per se snel. Het proefschrift laat zien dat veel van deze logica's alleen door extreem trage algoritmen kunnen worden bepaald — zo traag dat zelfs enorm snelgroeiende wiskundige functies nodig zijn om hun moeilijkheidsgraad te beschrijven, zoals de Ackermann-functie, waarvan de uitkomsten in vijf stappen exploderen van 1 naar een getal met 20.000 cijfers. Ook zet het een stap in een decennialang openstaande vraag over de exacte complexiteit van een bekend fuzzy-logicasysteem. Al met al werpt Deel 1 licht op de wisselwerking tussen expressiviteit en rekenkundige complexiteit.
Deel 2 draagt bij aan de theorie van well-quasi-orders, wiskundige hulpmiddelen die helpen aantonen dat algoritmen stoppen en meten hoe lang dat duurt. Deze hulpmiddelen zijn essentieel voor de resultaten uit Deel 1.
Deel 3 breidt een bekende techniek voor het definiëren van berekenbare functies zonder verwijzing naar fysieke machines uit naar een abstractere context met oneindige ordinale getallen. Dit levert een nieuwe manier op om een klassieke hiërarchie van berekenbare functies te begrijpen, en toont precies hoe "grotere" oneindigheden in de recursie overeenkomen met meer rekenkracht.