A matematikusok Nobel-díjaként jegyzett Abel-díjat kapta Lovász László, az MTA volt elnöke

A számítási bonyolultság elmélete – amely az algoritmusok sebességével és hatékonyságával foglalkozik – az 1970-es években még gyerekcipőben járt, de ma már mind a matematika, mind az elméleti számítógép-tudomány elismert területe. A hetvenes években a matematikusok új nemzedéke felismerte
a diszkrét matematika gyakorlati alkalmazásának új lehetőségeit a számítógép-tudományban. A számítási bonyolultság gyakorlati jelentősége megnőtt, és ma már az internetbiztonság elméleti alapjaként tekintünk rá, az elméleti számítógép-tudomány új eredményeit pedig a hatékony algoritmusok tervezésénél használják.

„Lovász és Wigderson az elmúlt évtizedekben vezető szerepet játszott ebben
a fejlődésben. Tevékenységük sok szempontból összefonódik, hiszen munkásságuk meghatározó volt a számítási véletlenszerűség megértése és
a hatékony számítás határainak kutatása szempontjából – mondja Hans Munthe-Kaas, az Abel-bizottság elnöke. – Kettőjük iránymutatásának köszönhetően a diszkrét matematika és a viszonylag fiatal elméleti számítógép-tudomány a modern matematika központi területeivé vált.”

Lovász László

Az 1948-ban Budapesten született, tizenéves kora óta „sztármatematikusként” emlegetett Lovász László munkássága összeköttetést teremtett a diszkrét matematika és a számítógép-tudomány között. Tudományos publikációi mellett számos könyv szerzőjeként ismert, műveiben mindig világosan és érthetően fogalmaz. Inspiráló előadó és vezető, aki egy cikluson keresztül (2007-től 2010-ig) a Nemzetközi Matematikai Unió elnöki tisztét is betöltötte.

Lovász LászlóFotó: mta.hu / Mudra László

Az 1970-es években a gráfelmélet volt a tiszta matematika egyik első olyan területe, ahol megmutatkoztak a számítási bonyolultság elméletének sajátos problémái és lehetőségei. Lovász munkásságának egyik legfontosabb eredménye, hogy meghatározta, hogyan képes a diszkrét matematika megoldani a számítógép-tudomány alapvető elméleti kérdéseit. Később valahol úgy nyilatkozott, nagyon szerencsés volt, hogy részese lehetett
egy olyan időszaknak, amelyben a matematika teljesen együtt fejlődött
egy alkalmazási területtel.

A számítógép-tudományt megalapozó munkája mellett Lovász László széles körben alkalmazható, hatékony algoritmusokat is kidolgozott. Ezek egyike
a róla, valamint az Arjen Lenstra és Hendrik Lenstra testvérpárról elnevezett LLL-algoritmus, mely fogalmi áttörést jelentett a rácsok megértésében, amelyek figyelemre méltóan jól alkalmazhatók többek között a számelmélet,
a kriptográfia és a mobil számítástechnika területén. A jelenleg ismert titkosítási rendszerek, amelyek képesek ellenállni egy kvantumszámítógép támadásának, az LLL-algoritmuson alapulnak.

Lovász László számos díjat kapott, köztük az 1999-es Wolf-díjat, az 1999-es Knuth-díjat, a 2001-es Gödel-díjat és a 2010-es Kiotó-díjat.

• Lovász László életpályájáról részletesebben
• Rövid összeállításunk az MTA elnökeként elért eredményeiről

Avi Wigderson

Avi WigdersonForrás: IAS/Cliff Moore

Avi Wigderson arról ismert, hogy képes meglátni az összefüggéseket
a matematika egymástól látszólag távoli területei között is. Wigderson
az izraeli Haifában született 1956-ban. Munkásságának fontos eredménye, hogy elmélyítette a matematika és a számítógép-tudomány kapcsolatát. Emellett alighanem mindenki másnál többet tett az algoritmusok sebességével és hatékonyságával foglalkozó bonyolultságelmélet területének bővítéséért és mélyebb kidolgozásáért.

Wigderson kutatásai a bonyolultságelmélet minden jelentősebb, megoldatlan problémáját felölelték, így nem vitás, hogy központi szerepet játszott
a matematika e területének fejlődésében. Több mint 100 tanulmány társszerzőjeként ismert.

A bonyolultságelmélet legfontosabb mai alkalmazása a kriptográfia. Pályafutása elején Wigderson meghatározó szerepet játszott ezen a területen, így a nullaismeretű bizonyítás megalkotásában is, amelyet napjainkban
a kriptovalutákhoz kötődő technológiában alkalmaznak.

1994-ben Wigderson elnyerte a számítógép-tudományi Rolf Nevanlinna-díjat. Számos egyéb díja között szerepel a 2009-es Gödel-díj és a 2019-es Knuth-díj.

• Avi Wigderson életpályájáról részletesebben

Lovász László életpályája

A tizenéves kora óta „sztármatematikus” Lovász László az elmúlt fél évszázad egyik legkiemelkedőbb matematikusává vált. Munkássága összeköttetést teremtett a diszkrét matematika és a számítógép-tudomány között, segített kidolgozni a tudományos kutatás e két nagy és egyre fontosabb területének elméleti alapjait, ahogy azt is, hogyan alkalmazhatók ezek a gyakorlatban. Termékeny könyvíróként szolgálta a közösséget, művei világosak és közérthetőek, inspiráló előadó és vezető, és egy cikluson keresztül (2007-től 2010-ig) a Nemzetközi Matematikai Unió elnöki tisztét is betöltötte.

Az 1948-ban Budapesten született Lovász a fiatal magyar matematikusok aranygenerációjához tartozott, akit az ország egyedülálló iskolai matematikai kultúrája táplált. Egy budapesti középiskola első kísérleti osztályába járt, ahol
a tehetséges diákok speciális matematikaórákat hallgattak. Egyik osztálytársa Vesztergombi Katalin volt, akit később feleségül vett. Lovász remekelt, aranyérmet nyert az 1964-es, 1965-ös és 1966-os Nemzetközi Matematikai Diákolimpián, az utóbbi kettőn ráadásul maximális pontszámmal. Megnyert egy főműsoridőben futó magyar tévéműsort is, amelyben az üvegkalitkákban ülő diákok matematikai feladatokat kaptak.

Tizenévesen meghatározó élménye volt találkozása matematikai példaképével, Erdős Pállal, a nomád és híresen társaságkedvelő magyar matematikussal. Erdős lelkesen vont be másokat a felmerülő matematikai problémák megoldásába, és arra inspirálta Lovászt, hogy a „magyar stílusú kombinatorikán” dolgozzon, amely lényegében a gráfok tulajdonságaival foglalkozott. Ez nemcsak a kezdeti kutatási irányt jelölte ki Lovász számára,
de meghatározó volt azt a nyílt és együttműködő stílust tekintve is, ahogyan később a matematikához viszonyult.

Lovász László a budapesti Eötvös Loránd Tudományegyetemre járt. 1970-ben, 22 évesen kandidátusi fokozatot szerzett; ekkor már nemzetközi konferenciákon tartott előadásokat, és 15 publikációja jelent meg. A magyar rendszer furcsasága miatt csak 1971-ben diplomázott, egy évvel azután, hogy megszerezte kandidátusi fokozatát.

A kombinatorika a minták és a leszámlálási minták matematikája.
A gráfelmélet a kapcsolatok – például egy hálózatban fennálló kapcsolatok – matematikája. Mindkettő a „diszkrét” matematika fogalomkörébe tartozik, mivel a vizsgált tárgyaknak határozottan elkülöníthető értékeik vannak, vagyis nem simán változnak, mint például egy görbe mentén mozgó pont helyzete. Erdős szívesen tanulmányozta ezeket a területeket pusztán az intellektuális öröm kedvéért, és nem foglalkozott a gyakorlati hasznukkal. Lovász viszont, felismerve, hogy a diszkrét matematika izgalmas, új alkalmazási lehetőségeket kínál a számítógép-tudományban, a matematikusok új nemzedékének vezéralakjává vált.

Az 1970-es években a gráfelmélet volt a tiszta matematika egyik első olyan területe, ahol megmutatkoztak a számítási bonyolultság elméletének sajátos problémái és lehetőségei. Lovász munkásságának egyik legfontosabb eredménye, hogy meghatározta, hogyan képes a diszkrét matematika megoldani a számítógép-tudomány alapvető elméleti kérdéseit. „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” – mondja.

Széles körben alkalmazható, hatékony algoritmusok kidolgozásával
a számítógép-tudomány alapjainak lerakásához is hozzájárult. Ezek egyike
a róla, valamint az Arjen Lenstra és Hendrik Lenstra testvérpárról elnevezett LLL-algoritmus fogalmi áttörést jelentett egy alapvető geometriai objektum,
a rácsok megértésében, amelyek figyelemre méltóan jól alkalmazhatók többek között a számelmélet, a kriptográfia és a mobil számítástechnika területén. Jelenleg az egyetlen ismert titkosítási rendszer, amely képes ellenállni egy kvantumszámítógép támadásának, rácsokon alapul, és az LLL-algoritmust használja.

Az 1970-es és 80-as években Lovász Magyarországon élt: először az ELTE-n, majd a szegedi József Attila Tudományegyetemen dolgozott, ahol 1978-ban
a Geometria Tanszék vezetője lett. 1982-ben visszatért az Eötvös Loránd Tudományegyetemre, ahol a Számítógép-tudományi Tanszék vezetőjévé nevezték ki. Ezekben a korai évtizedekben fontos és szerteágazó hatású problémákat oldott meg a diszkrét matematika számos területén. Az egyik első jelentős eredménye 1972-ben a gráfelmélet régóta nyitott problémája,
a „perfektgráf-tétel” megoldása volt. 1978-ban megoldotta Kneser sejtését ugyancsak a gráfelmélet területén, de ezúttal meglepte kollégáit, és egy teljesen más terület, az algebrai topológia bizonyítási módszerét alkalmazta. 1979-ben megoldotta az információelmélet klasszikus problémáját,
a Shannon-féle ötszögproblémát.

Lovász László munkásságának fő témája úgy a kombinatorika, mint az algoritmustervezés terén a valószínűségi módszerek vizsgálata. Ezen
a területen a Lovász-féle lokális lemma az a felfedezés, amiről a legjobban ismerik, a valószínűségi kombinatorika fontos és gyakran használt eszköze, amelyet ritka objektumok létezésének megállapítására használnak, szemben
a szokványosabb módszerekkel, amelyeket gyakoribb objektumok esetén alkalmaznak. Lovász közreműködött egy korai, a véletlennel ellenőrizhető bizonyításokról (PCP) szóló nagy hatású tanulmány megírásában is, amely
a számítási bonyolultság egyik legfontosabb területévé nőtte ki magát.

1993-ban Lovászt a számítógép-tudomány és matematika William K. Lanman-professzorának nevezték ki a Yale Egyetemen. 1999-ben a Microsoftnál kezdett tudományos kutatóként dolgozni, majd 2006-ban visszatért az ELTE-re, ahol jelenleg is professzor.

Lovász László vendégtanár volt a nashville-i Vanderbilt (1972–73), a waterlooi (1978–79), a bonni (1984–85), a chicagói (1985), az ithacai Cornell (1985) és a princetoni (1989–93) egyetemen, és egy évet töltött a szintén princetoni
Institute for Advanced Study kutatóintézetnél (2011–12). A barátok és kollégák „Lacinak” hívják, szerénységéről, nagylelkűségéről és nyitottságáról ismert.
E tulajdonságai is alkalmassá tették arra, hogy különféle tisztségeket töltsön be a Nemzetközi Matematikai Unió vezető testületében (amelynek elnöke is volt) és a Magyar Tudományos Akadémián (amelynek 2014–2020 között látta el az elnöki tisztét).

Lovász László számos díjat kapott, köztük az 1999-es Wolf-díjat, az 1999-es Knuth-díjat, a 2001-es Gödel-díjat és a 2010-es Kiotó-díjat.

Feleségével, Vesztergombi Katalinnal – aki szintén matematikus, és kutatótársként is gyakran dolgoznak együtt – négy közös gyermekük és hét unokájuk van.

Forrás: Simons Alapítvány, interjú Lovász Lászlóval, 2013

Az MTA elnökeként

„Legfőbb feladatomnak azt tekintem, hogy a Magyar Tudományos Akadémia iránti nagy közbizalmat fenntartsam” – mondta 2014 májusában az MTA frissen megválasztott, huszadik elnökeként Lovász László. Az akkor 66 éves, nemzetközi hírű matematikus az elkövetkező hat évben – két elnöki cikluson keresztül – azért dolgozott, hogy az 1825-ben alapított Akadémia minél hatékonyabban járuljon hozzá Magyarország fejlődéséhez.

Multidiszciplináris kutatási programokat – Tantárgy-pedagógiai Kutatási Program (szakmódszertan), Nemzeti Víztudományi Program, agrárkutatási program, közegészségügyi program – indított. Ezek közül példaértékű és hazai viszonylatban is páratlan kezdeményezés volt a Tantárgy-pedagógiai Kutatási Program, amelyben kutatók és gyakorló pedagógusok dolgoztak korszerű tanítási módszerek fejlesztésén.

Legyen a jelenleginél több női akadémikus, növekedjen a nők aránya
a posztdoktorok és az MTA doktorai között, a közoktatásban pedig minél több lány érdeklődését sikerüljön felkelteni a matematika, a fizika és más természettudományi tárgyak iránt – ezek voltak annak a szintén Lovász László által kezdeményezett új testületnek, a Nők a Kutatói Pályán Elnöki Bizottságnak a fő célkitűzései, amely 2017-ben kezdte meg munkáját.
Az eredmény: már két évvel később, 2019-ben rendkívül magas számban kerültek nők az új akadémikusok közé.

Világszerte elismert tudósként a tudományos és tudománydiplomáciai együttműködések előmozdítását, a hazai és európai kiválósági programok támogatását és a magyar tudományosság nemzetközi képviseletét is rendkívül fontosnak tartotta. A World Science Forum (Tudományos Világfórum) üléseit 2015 és 2019 között vezette elnökként, az ő vezetésével alakult meg nemrég az Academia Europaea (Európai Tudományos Akadémia) budapesti központja.

Lovász László második elnöki ciklusában alakult meg a Fiatal Kutatók Akadémiája (FKA), amelynek célja, hogy az Akadémia testületeivel szorosan együttműködve részt vegyen az MTA tudományos tevékenységében, valamint képviselje a fiatal kutatók közösségét itthon és külföldön. Az FKA segíteni kívánja a fiatal kutatók szakmai fejlődését, illetve a kutatók és a társadalom közötti kapcsolat erősítését.

Lovász László határozottan fellépett az áltudományokkal szemben is. Ugyanakkor azt a meggyőződését hangoztatta, hogy adminisztratív eszközök helyett a tudomány népszerűsítésével kell a kutatóknak tenniük a minden tudományos alapot nélkülöző teóriák, hiedelmek ellen. Elnöksége alatt az MTA erősítette tudománykommunikációs aktivitását: megújította a Magyar Tudomány Ünnepe rendezvénysorozatát, és egy új, a leggyakoribb tévhiteket eloszlató honlapot indított tudomany.hu címmel.

Lovász László mindent megtett annak érdekében, hogy az Akadémiánál maradhasson a kutatóintézet-hálózat. Az MTA Közgyűlésének állásfoglalásával összhangban vezetőtársaival együtt az utolsó pillanatig érvelt emellett.

A Magyar Tudományos Akadémia 193. közgyűlésének záróeseményén vetítették le azt a filmet, amelyen Lovász László kollégái, barátai emlékeztek vissza hatéves vezetői munkájára.

Avi Wigderson életpályája

Amikor az 1970-es évek végén Avi Wigderson tudományos karrierje elindult,
a „számítási bonyolultság” elmélete – amely az algoritmusok sebességével és hatékonyságával foglalkozik – még gyerekcipőben járt. Wigderson alighanem mindenki másnál többet tett e tudományág bővítéséért és elmélyítéséért, és az akkoriban épp csak kialakulóban levő tárgykör mára a matematika és az elméleti számítógép-tudomány elismert területévé vált. Ráadásul a számítási bonyolultság jelentősége váratlanul megnőtt, és ma már az internetbiztonság elméleti alapjaként tekintünk rá.

Wigderson 1956-ban született az izraeli Haifában. 1977-ben felvételt nyert
a Technionba, az Izraeli Technológiai Intézetbe, ahol 1980-ban számítógép-tudományi diplomát szerzett. Posztgraduális tanulmányai miatt Princetonba költözött, PhD-fokozatát 1983-ban szerezte a Tanulmányok a kombinatorikai bonyolultság terén (Studies in Combinatorial Complexity) című disszertációjával, konzulense Richard Lipton volt. 1986-ban Wigderson visszatért Izraelbe, és
a jeruzsálemi Héber Egyetemen helyezkedett el. A következő évben segédtanári állást kapott, majd 1991-ben egyetemi tanár lett.

Az 1970-es években a számítástudomány elméletével foglalkozó szakemberek alapvető gondolatokat fogalmaztak meg a számítás természetéről, megalkották a P és az NP fogalmát. A P az a problémakör, amelyet
a számítógépek akár néhány másodperc alatt is könnyedén meg tudnak oldani, míg az NP olyan problémákat is magába foglal, amelyek alaposan feladják
a leckét a gépeknek, vagyis az ismert módszerekkel adott esetben több millió évbe telhet megtalálniuk a választ. A számítási bonyolultság alapkérdése az, hogy ezek a nehéz problémák könnyen megoldhatóvá tehetők-e, azaz igaz-e, hogy P = NP. A matematika világában jelenleg ezt tekintik az egyik legfontosabb, megoldásra váró kérdésnek.

Wigderson óriási előrelépést tett ezen a területen azzal, hogy
a véletlenszerűség szerepét vizsgálta a számítás elősegítésében. Egyes nehéz problémák megoldása megkönnyíthető olyan algoritmusokkal, amelyek alkalmazásakor a számítógép „pénzfeldobásra” hagyatkozik a számítás során. Ha azonban egy algoritmus pénzfeldobásra épül, akkor mindig fennáll annak
a lehetősége, hogy hiba csúszik a megoldásba. Wigderson először Noam Nisannal, majd később Russell Impagliazzóval kimutatta, hogy minden olyan gyors algoritmus esetében, amely képes pénzfeldobással megoldani egy nehéz problémát, létezik egy majdnem olyan gyors algoritmus, amely bizonyos feltételek teljesülése esetén nem szorul rá a pénzfeldobásos módszerre.

Wigderson kutatásai a bonyolultságelmélet minden jelentősebb, megoldatlan problémáját felölelték. Az ezen a területen elért fejlődés sok szempontból az ő személye köré összpontosult, nemcsak széles körű érdeklődése, de megközelíthető személyisége és az együttműködés iránti lelkesedése miatt is. Jóval több mint 100 tanulmánynál működött közre társszerzőként, és számos fiatal bonyolultságelméleti szakembert mentorált. „Hihetetlenül szerencsésnek tartom magam, hogy ebben a korban élhetek – állítja. – A [számítási bonyolultság] fiatal terület. Nagyon demokratikus terület. Rendkívül barátságos, együttműködő, a természetemnek megfelelő terület. Ráadásul az is tény, hogy intellektuális problémák és kihívások sokaságát kínálja.”

1999-ben Wigderson belépett a princetoni Fejlett Tanulmányok Intézetéhez (IAS), ahol azóta is tevékenykedik. 2016-ban a Wigderson 60. születésnapját ünneplő rendezvényen az IAS igazgatója, Robbert Dijkgraaf úgy fogalmazott, hogy Wigderson érkezésével az elméleti számítógép-tudomány aranykora vette kezdetét az intézetben.

Wigderson arról ismert, hogy képes meglátni az összefüggéseket az egymástól látszólag független területek között is. Elmélyítette a matematika és
a számítógép-tudomány kapcsolatát. Ennek egyik példája az Omer Reingolddal és Salil Vadhannal közösen kifejlesztett „cikcakk-gráfszorzat”, amely összekapcsolja a csoportelméletet, a gráfelméletet és a bonyolultságelméletet, és meglepő célokra alkalmazható, így például segíthet meghatározni a legjobb módját annak, hogyan találjunk ki egy labirintusból.

Jelenleg a bonyolultságelmélet legfontosabb alkalmazási területe
a kriptográfia, amelyet az interneten tárolt információk, például hitelkártyaszámok és jelszavak biztosítására használnak. A kriptorendszerek tervezőinek például meg kell győződniük arról, hogy a rendszerük dekódolásának feladata NP-probléma, vagyis olyan, amelyet a számítógépek csak évmilliók alatt tudnak megoldani. Pályafutása elején Wigderson meghatározó szerepet játszott a kriptográfia új koncepciója, a nullaismeretű bizonyítás megalkotásában, amelyet most, több mint 30 év elteltével
a blokklánc-technológiában alkalmaznak. A nullaismeretű bizonyítás esetében két embernek anélkül kell igazolnia egy állítást, hogy az állítás érvényességén túlmutató bármilyen ismeretet feltárnának: ilyen eset például a két milliomosé, akik úgy akarják bebizonyítani a másiknak, hogy gazdagabbak nála, hogy közben nem árulják el, mekkora is a vagyonuk valójában. Wigderson Oded Goldreichhel és Silvio Micalival együtt kimutatta, hogy a nullaismeretű bizonyítás segítségével a titkos adatokkal kapcsolatos bármely nyilvános eredmény bizonyítható a titkosság megőrzése mellett. Tegyük fel például, hogy be akarjuk bizonyítani valakinek, hogy bebizonyítottunk egy matematikai tételt, de nem akarunk részleteket elárulni arról, hogyan csináltuk –
a nullaismeretű bizonyítással ez is lehetséges.

1994-ben Wigderson elnyerte a számítógép-tudományi Rolf Nevanlinna-díjat, amelyet a Nemzetközi Matematikai Unió négyévente ítél oda. Számos egyéb díja között szerepel a 2009-es Gödel-díj és a 2019-es Knuth-díj.

Wigderson felesége Edna, akivel a Technionban ismerkedett meg, és aki
a Fejlett Tanulmányok Intézetének számítástechnikai osztályán dolgozik. Három gyermekük és két unokájuk van.

Forrás: Heidelberg Alapítvány-díjasok portréi, interjú Avi Wigdersonnal, 2017