Az idei Abel-díjazottak nevét március 17-én jelentették be, és a nyertesek személyét az utolsó pillanatig nagy titok övezte – Lovászt például egy Zoom-álinterjú keretében tájékoztatták, hogy számos nemzetközi matematikai díj után az Abel-díjat is megkapja. A 2003-ban alapított díjnak Lovász a harmadik magyar születésű elnyerője: 2005-ban Lax Péter alkalmazott matematikus, 2012-ben pedig Szemerédi Endre, az elméleti számítógép-tudomány egy másik pionírja, nyerte el a nagy presztízsű kitüntetést.
Ahogy már említettük Lovász László, a Magyar Tudományos Akadémia előző elnöke, a budapesti Eötvös Loránd Tudományegyetem professor emeritusa, a Rényi Alfréd Matematikai Kutatóintézet kutatóprofesszora, és az izraeli születésű Avi Wigderson, a princetoni Fejlett Tanulmányok Intézete (USA) munkatársa szintén ezen a területen végzett munkásságáért érdemelte ki a díjat. Ami Wigderson elmondása szerint azért is nagyon fontos, mert az Abel-díj így ennek a tudományterületnek az alapvető fontosságát is megerősíti, amelynek az internetbiztonságtól a hálózatok tanulmányozásáig számtalan alkalmazási területe van.
Az algoritmusok kapcsán a számítógépek 20. századi bonyolódásával a vonatkozó problémafelvetés is átalakult.
A kezdeti lépések után már nem az volt a fő kérdés, hogy vajon van-e olyan algoritmus, amellyel megoldható egy probléma, hanem hogy van-e olyan algoritmus, amely elméletileg egy tényleges számítógépen, értelmezhető időkereten belül képes megoldást találni.
Lovász és Wigderson kulcsszerepet játszottak ebben a folyamatban a bonyolultságelmélet és az algoritmusok sebessége kapcsán végzett elméleti kutatásaik révén.
Gráfok és lemmák
Lovász 1948-ban született Budapesten, és fiatal korától meghatározó hatással volt rá Erdős Pál, a 20. század egyik legkiemelkedőbb matematikusa. Erdős munkásságának fontos területét jelentette a diszkrét matematika, amely véges objektumokkal és ezek kapcsolatával, például egy hálózat csomópontjaival foglalkozik. (Szemben például a folytonos változókkal dolgozó geometriával.)
Mire Lovász, aki igazi csodagyerek volt, és már 22 évesen kandidátusi fokozatot szerzett, kutatni kezdett, a területet korábban lenéző tiszta elméleti matematikai képviselői számára is egyre világosabbá vált, hogy a diszkrét matematika milyen fontos elméleti és gyakorlati jelentőséggel bírhat, többek közt a nagy adathalmazok elemzése során. Lovászt, ellentétben Erdőssel, aki tisztán az elméleti vonalon dolgozott, mindkét kutatási vonal érdekelte, így például hét évet a Microsoftnál is eltöltött különböző egyetemi pozíciói mellett. Ahogy mondja:
„Nagyon szerencsés voltam, hogy egy olyan időszakban tevékenykedhettem, amelyben a matematika teljesen együtt fejlődött egy gyakorlati alkalmazási területtel.”
Pályája során több fontos gráfelméleti problémát megoldott, így például igazolta a gyenge perfektgráf-sejtést és a Kneser-gráfokra vonatkozó sejtést is. Nevéhez fűződik továbbá a Lovász-féle lokális lemma, a valószínűségi kombinatorika egyik gyakran alkalmazott eszköze. Legfontosabbként számontartott eredményeinek egyike pedig az az algoritmus, amelyet Arjen és Hendrik Lenstrával közösen dolgozott ki.
Az LLL-algoritmus hatékony megoldást jelent a racionális együtthatós polinomok felbontására, vagyis lehetővé teszi, hogy egy alapvetően nagyon komplex matematikai kifejezést egyszerűbb kifejezések szorzatává bontsanak fel. Ez az elméleti matematika mellett kriptográfiában is nagyon jól alkalmazhatónak bizonyult. Az LLL-alapú titkosítás ráadásul jelenleg az egyetlen olyan rendszer, amely elvileg a jövőben képes lehet ellenállni a kvantumszámítógépek támadásának is.
Véletlenszerűség és nullaismeret
Wigderson 1956-ban Haifában született, majd Izraelben és az Egyesült Államokban végezte tanulmányait. Ezt követően különböző egyetemeken kutatott, míg végül 1999-ben Princetonban helyezkedett el. Az Abel-díj indoklása szerint a számítógép-tudomány gyakorlatilag minden területéhez hozzájárult, és a legtávolibbnak tűnő problémák megoldásába is szinte „fertőző” lelkesedéssel vetette bele magát.
Munkásságának egyik sarokköve a véletlenszerűség szerepének tisztázása volt a számítások során. Számos helyzetben, például amikor egy labirintusból kell kiutat találni, egy véletlenszerűségen alapuló (virtuális pénzérméket feldobó) algoritmus hamarabb talál megoldást, mint ha a rendszer következetesen végigpróbálna minden lehetséges útvonalat. Az azonban, hogy ez valóban így van-e, nem magától értetődő.
Wigderson az 1990-es években azonban kollégáival sikeresen igazolta, hogy minden gyors algoritmus esetében, amely a véletlenszerűséget is alkalmazza egy probléma megoldására, lennie kell egy majdnem olyan hatékony algoritmusnak, amely nem alapoz a véletlenszerűségre. Ezzel azt erősítette meg elméleti szinten, hogy a véletlenszerű algoritmusok valóban képesek helyes és gyors megoldásokat adni.
A kutató másik nagyon fontos eredménye azóta a kriptográfiában nyert gyakorlati alkalmazást. A Wigderson által megalkotott nullaismeretű bizonyítást jelenleg a blokklánc-technológiában alkalmazzák.
A bizonyítás lényege, hogy úgy igazolja egy állítás helyességét, hogy annak tartalmáról bármit is feltárna.
(Vagyis például lehetővé teszi, hogy így bizonyítsuk, megoldottunk egy fontos matematikai problémát, hogy közben nem kell feltárnunk, hogyan jutottunk a megoldásra.) Az ilyen bizonyítások nélkül elképzelhetetlen lenne ma a kriptovaluták létezése, de az egyéni azonosítás kapcsán is fontos ez a technika. Például egy ellenőrző kérdés megválaszolásával nullaismeretű bizonyítékát adhatjuk annak, hogy birtokában vagyunk egy jelszónak anélkül, hogy feltárnánk magát a jelszót.
***
A Norvég Tudományos Akadémia 7,5 millió svéd korona (körülbelül 271 millió forint) pénzjutalmat oszt szét az Abel-díj nyertesei között, akik személyéről minden évben egy öttagú, nemzetközileg elismert matematikusokból álló bizottság dönt.
