Avi Wigderson és Lovász László a komplexitás-elmélet és a gráfelmélet fejlesztéséért, valamint a két terület összekapcsolásáért nyerte el az Abel-díjat.

Amikor Avi Wigderson és Lovász László az 1970-es években megkezdték karrierjüket, az elméleti informatika és a tiszta matematika szinte teljesen külön tudományterület volt. Mára olyan közel kerültek egymáshoz, hogy nehéz közöttük megtalálni a határt. A mindkét területen végzett alapvető hozzájárulásukért és az őket összefogó munkájukért Lovász és Wigderson Abel-díjat kaptak, amelyet a Norvég Tudományos és Irodalmi Akadémia adományozott, és amelyet a matematika egyik legnagyobb kitüntetésének tekintenek.

„A zsenik és csillagok országában, Magyarországon ő már igen fiatal kora óta ragyogott. Nekem sok magyar barátom van, és mindegyik jól emlékszik rá, mint diákra.” „Ha a munkásságát tekintjük, nehéz elhinni, hogy mindezt egyetlen ember írta. Mestere az írásnak – mondja Widgerson, polcáról Lovász egyik korai művét (Combinatorial Problems and Exercises, 1979) leemelve. – Ez a könyv óriási hatással volt a kombinatorikára. Az első részben a problémák a diszkrét matematika témái szerint kerülnek osztályozásra, a középső rész az összes problémával kapcsolatos tippeket tartalmazza, az utolsó rész pedig mindre komplett megoldásokkal szolgál. Nagyon kiemelkedő mű, és még nem volt 30 éves, amikor írta.”

Lovásznak a diszkrét matematika szinte valamennyi területén komoly eredményei vannak. „És ez igen nagy terület – mondja Widgerson –. De a legtöbben, akik ezzel foglalkoznak, a területen belül maradnak, ő viszont módszereket vett át a topológiából, az algebrából és a geometriából. Számos eszközt hozott be ebbe a még ma is eszközökben szegény területbe.” Lovász: „Azt szeretem a legjobban, ha váratlan összefüggésre bukkanok valamilyen látszólag távoli területtel.”

„Munkájuk sok szempontból kiegészíti egymást. Avi az informatika, Lovász pedig a matematika oldalán áll, de sok kérdés, amelyen dolgoznak, összefügg” – mondja Russell Impagliazzo, a Kaliforniai Egyetem (San Diego) informatikusa, aki mindkét kutatóval együttműködött.

Hogy ez a párosítás megtörténhetett, a tudománytörténet azon egyedülálló időszakának eredménye, amelyben mindketten felnőttek.

Wigderson 1956-ban született az izraeli Haifában. Tizenéves korára az informatikusok még csak elkezdték felvázolni az alapvető elméleti kereteket, amelyek végül lefoglalják szakmai életét. Ez a komplexitás-elméletnek nevezett keretrendszer magában foglalja a számítási problémák osztályozását annak alapján, hogy mennyire nehezen oldhatók meg az algoritmusok. A nehézség elsődleges mértéke a számítási lépések száma, a legalapvetőbb megkülönböztetés a „könnyű” és a „nehéz”.

Könnyű számítási problémára példa két szám összeszorzása. Nem számít, mekkora a szám, a számítógépek gyorsan megtalálják a szorzatukat. Ez a probléma a „P” nevű komplexitási osztályba tartozik, amely minden könnyen megoldható számítási problémát tartalmaz.

Ezzel szemben egy szám prímtényezőinek megtalálása a nehéznek tűnő számítási probléma példája. Nincs olyan ismert algoritmus, amely képes lenne az összes számra gyorsan elvégezni. De ha valaki megadja nekünk a szám prímtényezőit, akkor egyszerűen meggyőződhetünk arról, hogy valóban a helyes tényezők, összeszorozva őket [ez szükséges, de nem elégséges, mert az is ellenőrzést igényel, hogy a tényezők valóban prímek – a fordító megjegyzése]. Ez a probléma az „NP” nevű komplexitási osztályba tartozik, amely olyan számítási problémákat tartalmaz, amelyeket nehéz megoldani, de amelyek válaszait könnyű ellenőrizni.

Az 1970-es évek elején a számítástechnikusok megfogalmazták az irányadó sejtést a számítási komplexitás területén: arra kérdeztek rá, hogy a P-ben szereplő problémák listája pontosan megegyezik-e az NP problémáinak listájával.

Ez a kérdés 1977-ben, amikor Wigderson belépett az Izraeli Technológiai Intézetbe, a Technionba, még friss volt. Az elkövetkező évtizedekben számos alapvető hozzájárulást tesz hozzá a komplexitáselmélethez: segít kidolgozni, hogy mely problémák mely körülmények között melyik komplexitásosztályba tartoznak.

Avi unokájával

„Amikor elkezdtem az egyetemet, a számítási komplexitás kezdett kiforrott területté fejlődni. Jómagam is együtt fejlődtem vele” – mondta Wigderson.

Az 1980-as évek végén Wigderson és munkatársa, Ran Raz a „tökéletes illesztés” probléma (ez a kérdés Lovász munkájában is megjelenik) számítási összetettségét tanulmányozta. Tegyük fel, hogy van 20 gépe, amelyek mindegyike képes 20 különböző feladatból néhány – de nem mindegyik –végrehajtására. A tökéletes illesztési probléma a következő: rendelhet-e gépeket feladatokhoz úgy, hogy minden feladat le legyen fedve, és minden gép pontosan egyet végezzen.

Wigderson és Raz a problémát bizonyos korlátozásokkal kiegészítve tanulmányozták. Azt képzelték, hogy a problémán dolgozó számítógépes áramkör képes a legtöbb szokásos számítási műveletre (például „és” és „vagy”), de nem képes egy döntő fontosságú műveletet végrehajtani: a „nem” műveletet.

Természetesen az informatikusok legszívesebben ’kvalifikálás’ nélkül szeretnék bizonyítani, hogy adott számítási kérdés nehéz. De eddig ez nem sikerült nekik (különben tudnánk, hogy P egyenlő-e NP-vel). Ezért inkább azt próbálják bebizonyítani, hogy egy olyan problémára, mint az illesztés, nem létezik gyors algoritmus, ha a számítási erőforrásokat, valamint a megoldására rendelkezésre álló időt korlátozzuk.

„Meg akarjuk találni az algoritmusok korlátait, és ha ezt a legáltalánosabb körülmények között nem tudjuk megtenni, akkor korlátozzuk őket” – mondta Wigderson. 1990-ben ő és Raz bebizonyította, hogy a „nem” művelet nélkül nincs jó módszer arra, hogy sok számítógépet párhuzamosan használjanak az áramkörök illesztési problémájának megoldására.

Wigderson új könyvének borítója. A könyv jelenleg szabadon letölthető itt: https://www.math.ias.edu/avi/book

Körülbelül ugyanebben az időben Wigderson a komplexitás egy központi kérdésén dolgozott: hogyan változtatja meg a véletlenszerűség a számítási problémák megoldásának sebességét. Az informatikusok az 1970-es évek óta gyanították, hogy a véletlenszerűség előnyt jelent. Megállapították: ha megengedjük egy algoritmusnak, hogy döntési folyamata során lényegében érméket dobjon fel, akkor sokkal gyorsabban tudunk megoldást találni bizonyos problémákra – például egy szám prím voltának tesztelésére –, mint ha azt írjuk elő, hogy az egyes lépéseket determinisztikusan válassza meg.

„Ez volt az a kor, amikor úgy tűnt, hogy sokkal több mindent tudunk tenni a véletlenszerűséggel, mint nélküle”.

De két, az 1990-es években megjelent cikkben Wigderson és munkatársai bebizonyították, hogy bizonyos feltételezések mellett mindig lehetséges egy erősen véletlenszerű algoritmust erősen determinisztikussá konvertálni. Megállapítást nyert, hogy a „BPP” néven ismert komplexitási osztály pontosan megegyezik a P komplexitási osztállyal. A véletlenszerű algoritmusok évtizedes munkáját szépen összekapcsolta a komplexitáselmélet központi részével, és megváltoztatta az informatikusok véletlenszerű algoritmusokra vonatkozó látásmódját.

„Azt hiszem, hogy ma szinte bárki, akitől megkérdezné, azt mondaná, hogy a véletlenszerűség inkább gyenge, mintsem erőteljes, mert olyan feltételezések mellett, amelyekben erősen hiszünk, a véletlenszerűség kiküszöbölhető”.

Wigderson, aki 1999 óta dolgozik az Institute for Advanced Study-ban, hosszú listát készített a komplexitáselmélet további eredményeiről, köztük a cikkcakkszorzatnak (zig-zag product) nevezett technikáról, amely közvetlenül kapcsolódik a tiszta matematika több területéhez, és stratégiát nyújt a labirintusból való meneküléshez, miközben csak rögzített számú kereszteződést tart észben. Wigderson munkájának kiterjedtsége is tükrözi, hogyan bővült a számítási komplexitás területe az ő pályakezdése óta.

„Avi nagyon központi figura ezen a mezőn” – állítja Impagliazzo. „Egyike azoknak, akik ezt konzisztens szakterületként tartják egyben. Emellett a terület kibővülése során is mindvégig világos szemlélettel rendelkezett."

Abban az időben, amikor Wigderson kiterjesztette a komplexitás-elmélet határait, Lovász egy szorosan kapcsolódó területen dolgozott, amelynek szintén sok lehetősége volt a növekedésre.

*

Az 1948-ban Budapesten született Lovász már kiskorától kezdve matematikai sztár volt. Tinédzserként három aranyérmet szerzett a Nemzetközi Matematika Olimpián, és egy olyan magyar TV-show-ban is diadalmaskodott, amely matematikai csodagyerekeket helyezett üveggel elszigetelt fülkékbe, hogy ott bonyolult problémákat oldjanak meg.

Szintén fiatal korában ismerkedett meg Lovász a befolyásos magyar matematikussal, Erdős Pállal, aki segített neki betekintést nyerni a gráfelmélet rejtelmeibe. Abban az időben a gráfelmélet matematikai holtág volt, amely olyan szórakoztató problémákat vet fel, mint a négyszín-sejtés (ma már bebizonyított tétel), amely azt kérdezi, hogy mindig lehetséges-e bármely térképen az országokat négy színnel színezni úgy, hogy két szomszédos ország ne legyen azonos színű.

„Homályosnak nem nevezném, de az bizonyos, hogy a gráfelmélet nem tartozott a matematika fősodrához, mert sok probléma vagy eredmény rejtvényekből vagy egyfajta szórakoztató matematikából származott” – nyilatkozta Lovász, aki jelenleg az ELTE professzora, az MTA volt elnöke. De a dolgok már változóban voltak, amikor Lovász 1970-ben, 22 évesen megszerezte doktorátusát, és ennek fő oka a számítógép-tudomány születése és gyors fejlődése volt.

A számítógépek kénytelenek diszkrét mennyiségekkel, 1-ekből és 0-kból álló bináris jelsorozatokkal dolgozni. A kombinatorika a diszkrét objektumok matematikája, és egyik fő részterülete a gráfelmélet, amely csúcsokat (pontokat) összekötő élek (vonalak) hálózatait tanulmányozza. Mint ilyen, egyfajta nyelvet biztosított az elméleti számítógép-tudományban felmerülő kérdések vizsgálatához.

Lovász a számítógépek és a gráfelmélet térnyerését kedvező történelmi egybeesésnek tekinti, hasonlóan ahhoz, ahogyan több mint egy évszázaddal azelőtt az analízis (a differenciál- és integrálszámítás fejlettebb formája) sürgős fizikai kérdések vizsgálata révén lépett érett korba.

„Néha a XVIII. és XIX. századi analízis és fizika analógiáját használom: ezek is kéz a kézben fejlődtek. Valami hasonló történt a gráfelmélet és az informatika terén.”

Lovász László és felesége, Vesztergombi Katalin 

Lovász munkájának komoly részét teszi ki a különféle problémák megoldására szolgáló algoritmusok kifejlesztése. Egyik legnagyobb hatású eredménye az LLL algoritmus, amelyet alkotóiról, Lovászról, valamint az Arjen és Hendrik Lenstra testvérpárról neveztek el. Az algoritmus a rácsoknak nevezett geometriai objektumokon működik: ezek a tér olyan pontjainak halmazai, amelyek koordinátáira vonatkozóan gyakori előírás, hogy egész értékeik legyenek. Az LLL algoritmus alapvető kérdést vet fel tulajdonságaikkal kapcsolatban: a rács melyik pontja áll legközelebb az origóhoz? Egyszerű kérdés, mégis gyakran nehéz megoldani, különösen a magasabb dimenziós terekben, és amikor a rács pontjai torz alakzatot hoznak létre.

Ahelyett, hogy pontosan megválaszolná a kérdést, az LLL algoritmus jó közelítést talál: azonosít egy pontot, és biztosítékot nyújt arra, hogy nincs más pont, amely sokkal közelebb lenne az origóhoz. A geometriai modell széles körű alkalmazhatósága miatt e pont megtalálásának képessége sokféle feladatnál szerephez jut, a polinomok faktorizációjától a kriptográfiai rendszerek biztonságának teszteléséig.

„Ez az egyik alapvető algoritmus. Elméletileg is fontos, és számos gyakorlati célra is alkalmazzák”, mondta az Erdős-díjas Gil Kalai, az IDC Herzliya és a jeruzsálemi Héber Egyetem munkatársa, aki korábban az Abel-díj bizottságnak is tagja volt. (Annak idején Gil Kalai izraeli matematikus Bárány Imrével (MTA Matematikai Intézet) együtt határozta el, hogy Lovászt fölterjesztik a Wolf-díjra. A jelöltek személyére izraeli egyetemek, tanszékek, könyvtárak, múzeumok tehetnek javaslatot, valamint az összes korábbi Wolf-díjas. Az alapfelterjesztő így Gil Kalai tanszéke lett.)

Lovász másik legjelentősebb hozzájárulása a valószínűséggel kapcsolatos. Az 1960-as években Erdős Pál kidolgozta a gráfokra vonatkozó kérdések megválaszolásának valószínűségi módszerét. A matematikusok gyakran tudni szeretnék, létezik-e bizonyos tulajdonságokkal rendelkező gráf. E kérdések megválaszolásának egyik módja az, hogy valóban talál egy ilyen gráfot. De Erdős rájött egy másik megközelítésre: elegendő, ha mindössze azt bizonyítjuk, hogy egy véletlenszerűen kiválasztott gráfnak nagy valószínűséggel megvan ez a tulajdonsága.

Erdős valószínűségi módszere legjobban a már közismert gráfok létezésének megállapításánál működött. Az 1970-es években Lovász Erdőssel közösen kidolgozott egy – Lovász-féle lokális lemmának nevezett – kiegészítő technikát, amely nagyon ritka gráfok létezésének bizonyítására szolgál. Ez azóta a terület egyik alapvető technikájává vált.

„Ez olyan eszköz, amelyet a későbbi bizonyításokban több százszor, több ezerszer alkalmaztak”, állítja Gil Kalai.

Lovász pályafutása során számos más problémát is megoldott a gráfelméletben, beleértve Kneser sejtését egy bizonyos gráf színezéséhez szükséges minimális színszámról, valamint egy olyan kérdésről, amely a gráfokban garantálja a tökéletes illeszkedést és a kapcsolódó struktúrákat. Több saját sejtést produkált, amelyek ma is irányt szabnak a gráfelméleti kutatásnak. Ide sorolható két probléma, a KLS-sejtés és az EFL-sejtés, amelyekkel kapcsolatban éppen az elmúlt hónapokban születtek nagy eredmények.

Ugyanazokban az években, amikor Wigderson és a hozzá hasonló úttörők tovább finomították a számítási komplexitás megértését, Lovász olyan, a gráfokkal kapcsolatos kérdésekre adott választ, amelyek segítettek meghúzni a határokat a különféle komplexitási osztályok között.

A tavaly újranyomtatott könyv itt megrendelhető

Kalai szerint „ezeket a komplexitási koncepciókat a gráfokkal kapcsolatos nagyon egyszerű kérdések jelenítették meg. Így igencsak előtérbe kerültek a gráfokkal kapcsolatos kérdések, és Lovász ezeket kezdettől fogva tanulmányozta.”

Ezért helyénvaló, hogy azt a két úttörőt, akik összekapcsolták területeiket, immár az Abel-díj is egymáshoz kösse.

Források: Kevin Hartnett (Quanta Magazine)

Egy optimális elme

Ford., szerk: Jakabffy Imre, Jakabffy Éva