Professorportræt: Nutan Limaye skubber til grænserne for beregningskompleksitet

Den 22. maj 2025 kl. 14:30 vil professor Nutan Limaye fra sektionen Theoretical Computer Science holde sin tiltrædelsesforelæsning i Auditorium 0 på IT-Universitetet i København. Forelæsningen har titlen: “My reflections on the last two decades and Complexity Theory”.

Skrevet 1. maj 2025 08:53 af Mette Strange Mortensen

Professor Nutan Limaye var med sine egne ord ”rimeligt god til matematik”, da hun gik i skole. Hun var draget mod algoritmer og så, hvordan de påvirkede mange ting i menneskets natur. Mennesker har en medfødt tendens til at designe effektive løsninger for hverdagens problemer. For eksempel vil vi ofte forsøge at finde den optimale rute fra punkt A til punkt B eller finde det bedste tilbud, når vi handler. Kombinationen af at være rimelig god til matematik og være glad for algoritmisk tænkning, fik hende til at finde vej ind i forskningsfeltet beregningskompleksitet.

Beregningskompleksitetsteori er et af grundforskningsområderne indenfor datalogi. Grundlaget for forskningsområdet kan findes i det tidlige arbejde fra den engelske matematiker Alan Turing, der opfandt Turing-maskinen og som er kendt for at være involveret i at bryde tyskernes koder under anden verdenskrig. Beregningskompleksitetsteori har tætte bånd til mange andre matematiske grene som for eksempel kombinatorik, sandsynlighedsteori og algebra.

"Min forskning er hovedsageligt teoretisk. Så på kort sigt kan det måske ikke synes at have nogen reel indvirkning. Men det har forbindelser til flere praktiske områder. For eksempel, når vi siger, at data er sikre, som når vi bruger et kreditkort, er det fordi dataene er krypteret og sendt gennem en sikker kanal. Kryptering fungerer ved at anvende en funktion på dataene, som er svær at invertere. Eksistensen af en funktion, der er 'svær at invertere', sikrer, at dataene ikke kan dekrypteres af en ondsindet modstander. Mit arbejde forsøger at bevise, at visse funktioner er svære at beregne, hvilket er ret afgørende for kryptografi," siger professor Nutan Limaye.

Den 22. maj 2025 kl. 14.30, vil Nutan Limaye afholde sin tiltrædelsesforelæsning på IT-Universitetet i København. Forelæsningen vil handle om hendes aktuelle forskning i beregningskomplekset, og har titlen: “My reflections on the last two decades and Complexity Theory”.

Banebrydende forskning leder til nye spørgsmål

Selvom kompleksitetsteori har eksisteret i lang tid, er der stadig meget mere at opdage inden for feltet.

”Mit nuværende arbejde fokuserer på at beregne polynomier og forsøge at forstå deres kompleksitet. Vi var i stand til at fastslå, at visse polynomier, som har effektive sekventielle algoritmer, ikke kan beregnes af effektive parallelle algoritmer. Det her hårdhedsresultat, som vi beviste i 2021, har givet anledning til mange nye spørgsmål." Siger Nutan Limaye om hendes seneste resultater.

En af de største udfordringer inden for algebraisk kompleksitetsteori er P vs. NP-problemet, eller VP vs. VNP-spørgsmålet, som det kaldes i relation til beregningspolynomier. Det er det primære område for Nutan Limayes forskning. Hendes seneste resultat tager et lille skrift mod at løse et stort åbent spørgsmål. Da hun bliver spurgt om, hvad der ligger forude, uddyber hun:

"Mit næste store spørgsmål er at undersøge, om træstrukturer er mere komplicerede end DAG-strukturer i forbindelse med beregning af polynomier. I en træstruktur tager man to objekter, kombinerer dem, derefter to andre objekter og kombinerer dem, og derefter tager man outputtet af de to og kombinerer dem, så det ligner et træ. I en DAG-struktur kan en beregning genbruges flere gange, ikke kun én gang. Dette kunne ligne en ejendom, der ejes af flere personer, hvilket gør strukturen mere kompleks. Selvom DAG-strukturen ser mere kompliceret ud end træstrukturen, ved vi ikke, hvordan vi kan bevise det matematisk i forbindelse med beregning af polynomier."

Skulle slet ikke have været forsker

Nutan Limaye har arbejdet som forsker i 20 år.

"Jeg endte i det her felt ved et tilfælde. Da jeg havde afsluttet min grunduddannelse, følte jeg et pres for at finde et job og slå mig ned, og det ville jeg ikke. Løsningen var at fortsætte med at studere, og så var der muligheden for at tage en ph.d., så det gjorde jeg i stedet,” fortæller professor Nutan Limaye.

I sine første år som forsker var hun ikke sikker på, om hun passede ind i akademia. For at udfordre stereotyperne om, hvordan en forsker ser ud, har hun startet sin egen podcast, hvor hun interviewer andre forskere om, hvordan de nåede dertil, hvor de er, og hvad der holder dem i gang. Hendes podcast hedder ”Life of a researcher”.

"De første par år af mit forskningsliv undrede jeg mig altid over, 'hører jeg til her i akademia?'. Men nu har jeg fundet min plads. At være forsker giver mig meget selvbestemmelse og frihed i mit arbejdsliv. Jeg kan vælge at arbejde med det, der interesserer mig. Jeg håber, at den forskning, jeg vælger at lave, kan blive nyttig for verden," afslutter Nutan Limaye.