Naujienų archyvas

Abelio matematikos premija – skaičiavimų sudėtingumo specialistams

Kovo 17 dieną Norvegijos mokslo ir meno akademija paskelbė 2021 m. prestižinės Abelio premijos laureatų vardus. Norvegijos Vyriausybės įsteigta premija įteikta László Lovászui ir Avi Wigdersonui. Abu laureatai yra žymūs mokslininkai, kurių tematikos glaudžiai susijusios su Skaičiavimų sudėtingumo („Computational complexity“) teorija. Ši sritis, esanti matematikos ir teorinės informatikos sandūroje, tiria algoritmų greitį ir sudėtingumą. Didžiausią postūmį skaičiavimų sudėtingumo teorijos vystymuisi turėjo kertinis teorinės informatikos uždavinys – žymioji P vs. NP problema. Ji klausia, ar kiekvienas uždavinys, greitai patikrinamas (per polinominį laiką), gali būti ir greitai išsprendžiamas. Ši informatikų „dovana“ matematikams pasirodė tokia sudėtinga, kad 2000 m. buvo įtraukta į Klėjaus matematikos instituto septynių tūkstantmečio problemų sąrašą. Iki šiol ji neišspręsta, nors daugelis matematikų tiki, kad P ≠ NP.
Skaičiavimų sudėtingumo tematika ypač aktuali šiuo metu kalbant, pavyzdžiui, apie interneto saugumą. Šiuolaikinis interneto saugumo specialistas negali apsieiti ne tik be kriptografijos, algoritmų efektyvumo žinių, bet ir be skaičių teorijos, grafų teorijos ir abstrakčiosios algebros elementų. Būtent László Lovászas ir Avi Wigdersonas atskleidė gilų diskrečiosios matematikos (susiformavusios jau prieš daugelį dešimtmečių) ir žymiai jaunesnės teorinės informatikos ryšį.

László Lovász (kairėje, foto: Hungarian Academy of Sciences / Laszlo Mudra / Abel Prize) ir
Avi Wigderson (dešinėje, foto: Cliff Moore / Institute for Advanced Study, Princeton, NJ USA / Abel Prize)

L. Lovászas – Vengrijos matematikų mokyklos atstovas, išgarsėjęs savo pasiekimais kombinatorikoje ir grafų teorijoje, yra suformulavęs ne vieną uždavinį. Pavyzdžiui, grafų spalvinimo uždavinį (Erdős–Faber–Lovász hipotezė, kuri 2021 m. beveik išspręsta). Jis yra pelnęs Wolfo, Knutho (abi 1999), Gödelio (2001) ir Kioto (2010) premijas.
A. Wigdersonas yra puikiai žinomas matematikų ir informatikų bendruomenėje Izraelio mokslininkas dėl jo pasiekimų sudėtingumo, lygiagrečiųjų skaičiavimų, kriptografijos ir grafų teorijose. Yra Gödelio (2009) ir Knutho (2019) premijų laureatas.
Manyčiau, kad ši pelnyta Abelio premija yra stimulas ir Lietuvos matematikams bei informatikams, besidomintiems įvairiais skaičiavimų sudėtingumo aspektais.

Akad. Remigijus Leipus