A 2000-ben készült mélyinterjú első része itt olvasható.

Lovász László: Nagyon fontosnak tartom a matematikának és a tudományunkon kívüli intelligenciának a viszonyát. Itt rosszabb a helyzet, mint kellene. Ezt már a matematikus közösség is kezdi fölismerni. Nagyobb erőfeszítéseket kell tennünk arra, hogy érthetően elmagyarázzuk a nagyközönségnek: a matematika él, létezik, kiszakíthatatlanul benne foglaltatik mindennapjainkban. Amikor például CD-ROM-unkat a gépünkbe tesszük, ahhoz, hogy tökéletes minőségben fölcsendüljön a zene, komoly algebrai kódoláselméleti módszerek kellenek.

Staar Gyula: A modern matematika sikereinek közkinccsé tétele nehéz vállalkozás. A matematika nyelvét nem mindenki beszéli, érti. Szerencsés eset, amikor a nehéz probléma közérthetően megfogalmazható. Ezért lehetett a Fermat-sejtés megoldása jól előadható sikertörténet a médiában. A mai matematika legtöbb kérdésfelvetésének csupán a megértéséhez szinte egy kisebb kurzust kellene tartani.

L.L.: Azért, ha belegondolsz, a Fermat-sejtés megoldásában a döntő lépés az volt, amikor kiderült a kapcsolat a Shimura– Taniyama– Weil-sejtéssel, azaz sikerült átfogalmazni az alapkérdést az elliptikus egyenletek nyelvére. Így kerülhetett Andrew Wiles kezébe erős és hatékony eszköz, amelyet kihasználva legyőzte a több száz éves problémát. Ennek az eszközrendszernek a megvilágításához, természetesen, ahogyan mondtad, már külön kurzus kellene. Azért nem minden mai matematikai probléma ilyen. Éppen a számítógépekhez kötődően kerültek felszínre egyszerűen megfogalmazható alapvető problémák. Például felírok tízezer 0-ból és 1-ből álló sorozatot és odaadom neked, döntsd el, pénzfeldobással kaptam, avagy valamilyen más eljárással, algoritmussal generáltam. Becsaphatlak-e egy ilyen sorozattal...?

S.Gy.: Annyit azért tudok, legutóbb Laczkovich Miklós „Koincidenciák és egyéb kis valószínűségű események” cikkében is szó esett róla, hogy ha nincsenek benne hatos vagy hetes összefüggő, 0-ás vagy 1-es sorozatok, akkor minden bizonnyal nem véletlenszerűen állítottad össze a sorozatot.

L.L.: Így bukhatok le, de ezt én is tudom! Most azonban egy tesztet végzek veled. Ahhoz, hogy ebből matematikai probléma legyen, pontosan kell megfogalmaznom cselekvési lehetőségeinket. Az egyik, ha pénzdobással állítom elő, ez könnyű eset; a másik, amikor algoritmussal számolom a sorozatot. Itt már precízen meg kell fogalmazom, milyen algoritmust engedek meg magamnak. Ugyanakkor azt is pontosítanunk kell, te milyen algoritmust használhatsz ahhoz, hogy eldönthesd, a két sorozat közül melyiket miként állítottam elő. A mai számítógép-tudománynak ez a kérdés alapvető, megoldatlan problémája.

S.Gy.: Szakmád határához érkeztünk. Kérlek, vezess kissé beljebb minket. Mi az algoritmuselmélet? Miért vált ez a terület ma oly élővé és fontossá? Mik itt a legnehezebb kérdések?

L.L.: Nagyon egyszerű példával kezdem. Vegyünk egy pozitív egész számot, mondjuk a 17-et. Ez prímszám, mert nem írhatjuk fel két, nála kisebb pozitív egész szám szorzataként. A nem prímszámok fölbonthatók két, esetleg több prímszám szorzatára. Kérdés, miként lehet eldönteni egy pozitív egész számról, prím vagy sem. S ha már eldöntöttük, hogy összetett szám, akkor miként állíthatjuk elő felbontását prímtényezők szorzatára. Ezzel korábban kevesen foglalkoztak. 

Carl Friedrich Gauss (1777-1855)

Gauss ugyan megvizsgálta, ő azonban papíron számolt, így eleve viszonylag kis számokig juthatott. Az ötvenes, hatvanas években azután, ahogyan a számítógépek elterjedtek, egyre nagyobb számok hovatartozását döntötték el. Akkor ez a problémakör teljesen absztraktnak tűnt, hiszen miért is érdekelné az embereket, hogy mondjuk egy ötszáz jegyű szám prím vagy sem. A hetvenes évek végén villámcsapásszerűen jött a felismerés: a polgári célú kriptográfia, a vele szorosan összefüggő adatvédelem ennek a megválaszolhatóságán alapszik. A kulcskérdés tehát: miként lehet ellenőrizni, hogy ilyen szám prím-e – ez a viszonylag könnyebb feladat – , s ha már kiderült, hogy nem prím, akkor miként lehet felbontani tényezőire; ez a lényegesen nehezebb feladat. Megoldásán nagyon sokan dolgoznak, bevetve a számelmélet eddig kiépített nehézfegyverzetét.

Az utóbbi 10 évben sokat dolgoztam azon, hogyan lehet egy test térfogatát számítógéppel kiszámítani. A kérdés persze akkor érdekes, ha a test nem három, hanem sok dimenziós. Mindez csupán matematikai konstrukció. Már a század elején tisztázták, hogyan lehet definiálni, mérni magas dimenzióban egy lezárt területet. Amikor számítógéppel igyekeztek kiszámítani az ilyen test térfogatát, kiderült, hogy az eddig bevált egyszerű módszerek nem eredményesek. Három dimenzióban jól alkalmazható eljárás, hogy a testet egy csúcsától kiindulva egyszerűbb testekre bontom, azok térfogatát kiszámítom, majd összegzem. A dimenzió növekedésével azonban olyan sok kis test keletkezik, ami reménytelenül bonyolítja a számítást. Gyökeresen más módszerre van szükség a megoldáshoz.

Az algoritmuselmélet abból a kérdésből nőtt ki, miként is lehetne valamit számítógépen megcsinálni. Az egészben az a legérdekesebb, hogy ez a kérdésfelvetés, mely gyökeresen fölforgatja a hagyományokat, lezártnak hitt tudásunkat, olyan világot teremt, ahol az újak mellett nagymértékben igénybe vesszük a matematika mély, hagyományos eszközeit.

S.Gy.: Gondolom, az algoritmuselméletben nagyon sok olyan nehéz kérdés van, amit még csak próbálgattok megemelni.

L.L.: Igen. A legnehezebb kérdések azok, amelyekre a várható válasz az, hogy valószínűleg nem oldható meg hatékonyan számítógéppel. Semmilyen algoritmussal. Nagyon sok esetben gyanítjuk ezt, de nagyon kevésszer tudjuk bebizonyítani.

S.Gy.: Miért érdemes azt bebizonyítani, hogy valamely kérdésnek számítógéppel nem lehet a végére járni?

L.L.: Mert nagyon sok adatbiztonsági eszköz működése ennek a feltételezésén alapszik. Ezért lett alapvető fontosságú például az a semlegesnek tűnő kérdés, hogy egy 500 jegyű számot, ha arról kiderült, hogy nem prím, számítógépes programmal, nem csillagászati idő alatt fölbonthatunk-e tényezőire. Az egész bankrendszer összeomlana, ha valakinek sikerülne ilyen algoritmust írnia. Megfordítva is igaz: ha valaki bebizonyítaná, hogy ez nem lehetséges, ilyen algoritmus nem létezik, akkor a bankok nyugodtabban alkalmazhatnák biztonsági rendszerünkben az ezen alapuló adatvédelmi módszereket.

S.Gy.: Azt ugye már tudjuk, hogy vannak algoritmussal nem megoldható problémák.

L.L.: Már a harmincas években találtak ilyeneket. Ezek felismerése Albert Church (19. sz.) nevéhez fűződik. Esetünkben azonban finomabb mértékről van szó: algoritmussal, nem csillagászati idő alatt megoldható-e a feladat. Mert például a már említett 500 jegyű számot felbonthatom tényezőire algoritmussal. Egyszerűen veszem az összes, nála kisebb számot – persze ennél jóval kevesebbel is célhoz érek – , majd sorra veszem, osztó-e valamelyik, és kész a megoldás. „Mindössze” az a baj, hogy legfeljebb 500 jegyű számból több van, mint csillag az égen. Ilyen algoritmus szerinti számolás a világegyetem végezetéig sem fejeződne be. Az igazi kérdés tehát nem az, hogy a probléma egyáltalán megoldható-e algoritmussal, hanem az, hatékonyan megoldható-e. A hatékonyan azt jelenti, hogy reális idő alatt. E téren nagyon sok kérdés megválaszolatlan, szinte mindegyik az.

Katona Gyula

S.Gy.: Katona Gyula az Algoritmusok bonyolultsága című írását tanulságként egy „ördögi történettel” fejezte be. „A Sátán megkísérti a számítástudóst. – Pénzt adok, gazdagságot, tied lesznek a legszebb nők, a legjobb kocsik, ha engem szolgálsz. A tudós elgondolkodik, nagyon szeretne gazdag lenni, nem is szólva a nőkről. De a becsület! Mégis, van valami, amiért érdemes eladni a lelkét. – Rendben, a szolgád leszek, ha megmondod, hogy P = NP vagy nem, és ha nem, mi a megoldás? – Nagyszerű, nem vagy te olyan együgyű! – örvendezik a Sátán. Holnap hozom a megoldást. De se másnap, se a rákövetkező héten nem jön. Csak egy hónap múlva. – Nem megy! A Nagy Hacker mindig belép, leállítja a számításokat!” Szerinted se megy majd?

L.L.: Hát, a P = NP tényleg alapvető kérdése a matematikának.

S.Gy.: Mondanál erről valamivel többet?

L.L.: Nagyon sok olyan algoritmikus probléma van, aminél ha ráhibázunk a megoldásra, már könnyű ellenőrizni, hogy az jó-e. Például egy óriás számról szeretnénk eldönteni, hogy prímszám vagy sem. Ha rátalálunk egy osztójára, akkor egyszerű az ellenőrzés. A számítógép az osztást sok ezer jegyű számokkal is könnyen, gyorsan elvégzi. Temérdek matematikai feladatnak ugyanilyen a logikai szerkezete. Ezeket a problémákat nevezik NP-nek. Az NP a nemdeterminisztikusan polinomiális kifejezést takarja.

A kérdés az, ha egy probléma ilyen szerkezetű, abból következik-e, hogy hatékonyan kiszámítható. Tehát képesek vagyunk-e megkeresni azt, amit ha egyszer megtalálunk, már könnyen ellenőrizhetjük, hogy jó-e. Ez a P. A P = NP azt jelentené, hogy ilyen problémára, amit szokás kereső feladatnak nevezni, készíthető hatékony algoritmus. Ez a számítástudomány alapkérdése. A várt válasz: nem!

S.Gy.: A matematikusok többsége olyannyira hisz a nemben, hogy állítólag, amikor valaki negyvenoldalas cikkben a P=NP igazát vélte bizonyítani, senki sem vállalta az ellenőrzést. Sajnálták rá az időt. Csak három év múlva mutattak rá a hibára.

L.L.: A P = NP kérdése a hatvanas évek végén vetődött fel, s ahogyan az évtizedek múltak, lett egyre világosabb, mennyire nehéz. Ma úgy tűnik, hogy hagyományos eszközökkel ez a probléma megközelíthetetlen. Ugyanabban a cipőben lehetünk, mint a görög matematikusok, akik nem boldogultak a kockakettőzéssel, a szögharmadolással, a szabályos hétszög megszerkesztésével. Ahhoz, hogy Gauss bebizonyíthassa, a szabályos hétszög nem szerkeszthető, a matematikában hatalmas fogalmi változásnak kellett lezajlania. A geometria mellé kifejlődött az algebra, a valós és a komplex számok elmélete, az egyenletek megoldhatóságának kérdésköre. Mindezek a szerkeszthetőségtől függetlenül zajlottak. Azután egyszerre a kép összeállt, s ma már egy gimnáziumi szakkörön is nyugodtan végigmehetünk azon a gondolatsoron, hogy a szabályos hétszög miért nem szerkeszthető meg körzővel és vonalzóval. Ma ezt azért tehetjük meg, mert egykoron a matematikának a geometriától távol állónak hitt területén történt valami, felsejlett egy új világ. Úgy érzem, valami hasonlónak kell bekövetkeznie a diszkrét matematikában, a logikában is ahhoz, hogy válaszolhassunk arra, miért nem lehet P=NP. A „miért nem lehet” jellegű kérdéseket mindig sokkal nehezebb megválaszolni. Nincs meg a természetes hozzáállás, hiányoznak a megfelelő módszerek. A bizonyításhoz ki kell épülnie körülötte valaminek, valamilyen elméletnek, melynek segítségével általánosabban, átfogóbban tekinthetünk a kérdésre. Ma még nem tartunk itt.

S.Gy.: Mikor érünk oda?

L.L.: A matematikát sokan művelik, ezért fejlődése igencsak felgyorsult. Nem hiszem, hogy ez a probléma száz évig megoldatlan maradna. Talán ötven évig...

Staar Gyula

Az interjú harmadik része itt olvasható.