Det finnes problemer som vi ikke har klart å finne effektive algoritmer for, og hvilke problemer som vi har effektive algoritmer for, hvilke problemer er uhåndterbare og hvilke problemer er uløselige er et stort forskningsfelt. I denne podcasten snakker vi blant annet om klassene NP og P og forklarer hva det vil si at et problem er NP-komplett. Og vi snakker om stopp-problemet (halting problem) - kan maskinlæring brukes for å gå løs på dette problemet?

 

I denne episoden er Pinar Heggernes gjest. Akkurat nå er Pinar kanskje aller mest mest kjent for at hun er valgt til prorektor ved UiB. Hun er professor og instituttleder for Institutt for informatikk, hun sitter i styret i Norges Forskningsråd og er styreleder for NORA. Men hun er også en aktiv forsker innenfor fagfeltet “algoritmer” (inkludert kompleksitet, kjøretid, P=NP, effektive algoritmer som kan få dataprogram til å gå så raskt som mulig) og har blant annet forsket på problemer som er aktuelle i forbindelse med årets Abelpris: "kompleksitetsteori" – som handler om hvilke problemer som vi har effektive algoritmer for, hvilke problemer er uhåndterbare og hvilke problemer er uløselige.