Napok óta izgalomban tartja a matematikusokat egy felfedezés, ami a számítógép-tudományban hoz jelentős előrelépést. Abban a tudományágban, ami az információfeldolgozó gépek tervezésének és működtetésének elméleti, matematikai alapjaival foglalkozik. Egy magyar kutató, a Chicagói Egyetemen tanító Babai László olyan algoritmust alkotott, ami megoldást ad egy régi problémára, a gráfizomorfizmus-problémára. A megoldással mélyebben megérthetjük a számítástudomány lényegét, ez lehet a tudományág legfontosabb felfedezése ebben az évtizedben – lelkendezik a felfedezésről Scott Aaronson, a világ legjobb műszaki egyetemei közé tartozó MIT matematikusa. A gráfizomorfizmus-probléma kicsit leegyszerűsítve arra utal, hogy két gráf ugyanaz-e még akkor is, amikor máshogyan néznek ki. De mi az a gráf? A gráf a matematikai gráfelmélet és számítógép-tudomány egyik alapvető fogalma. A gráf a dolgok és a rajtuk értelmezett összeköttetések halmaza, megadhatjuk a csúcsainak és éleinek (az összeköttetéseket nevezzük így) felsorolásával, vagy diagram formájában, így kicsit szemléletesebb. Vagyis ha adva van két, egymástól látszólag különböző halmaz – teljesen mindegy, hogy mekkorák, hogyan vannak tagolva –, meg lehet mondani, hogy valójában ugyanolyanok-e (a fenti ábrán látható két gráf például ugyanolyan). A mostani megoldással jóval kevesebb lépéssel eljuthatunk ennek a felismeréséig. P-k és NP-k Ahhoz, hogy megértsük, mi a maga a probléma, néhány fogalommal kell megismerkednünk a modern komplexitáselméletből. A számítástudományban úgy is meg lehet különböztetni a problémákat egymástól, hogy mennyire bonyolult megoldani őket, vagyis hány lépéssel lehet eljutni a megoldásig. Vegyünk egy gráfot, és nézzük meg, hogy a csúcsai kiszínezhetőek-e úgy, hogy csak három színt használunk, és az egymás melletti csúcsok nem lehetnek azonos színűek. Ez a probléma akkor polinomikus (P), ha van olyan algoritmusunk, ami megmondja, hogy kiszínezhető-e a gráf ilyen módon. Ellenben NP osztályban van, ha nincs ilyen algoritmusunk, de valaki azt mondja, hogy létezik olyan megoldás, hogy azt polinominális időben ellenőrizni tudjuk (vagyis megmutatja, hogy ki tudja színezni úgy a pontokat). Nézzük egy kicsit gyakorlatiasabb példával illusztrálva! Tegyük fel, hogy meg akarjuk állapítani, hogy a 983 vagy a 105227 prímszám-e. A megoldáshoz vezető lépések lassan nőnek a számjegyek növekedésével, vagyis hiába háromjegyű az egyik és hatjegyű a másik szám, a megoldáshoz vezető lépések száma nem sokkal több a második esetben. A feladat megoldható polinominális idő alatt, tehát P osztályú a probléma. Egy másik példában meg akarjuk keresni a 2111231 szám összes osztóját. Eddig senki nem talált még polinominális algoritmust erre a feladatra, de megkereshetjük egyenként az osztókat. A probléma tehát az NP osztályban van. Itt a lépések száma exponenciálisan nő a számjegyek növekedésével, vagyis egy háromjegyű szám esetében sokkal-sokkal kevesebb lépéssel találjuk meg az összes osztót, mint egy hatjegyű számnál. Vagyis a P egyenlő NP (P=NP) probléma azt jelenti, hogy az NP problémák P-k, vagyis megoldhatóak. Azokat a feladatokat, amelyeket polinominális idő alatt meg tudunk oldani P-vel, amelynél csak a megoldás helyességé tudjuk ellenőrizni, NP-vel jelöljük. A P feladatok NP-k is, hiszen ha van megoldó algoritmus, akkor az bizonyítja azt is, hogy helyes a megoldás. De van egy olyan sejtés, hogy NP nem egyenlő P-vel, ez az P=NP probléma. Erre még nincs bizonyítás. (Csodálatosan átlátható leírást ad a problémára Lovász László matematikus, az MTA elnöke ebben a rövid történetben, ami Arthur király udvarába visz el minket.) Kevesebb lépéssel az eredményig Babai László Babai László most kimutatta, hogy a probléma, ami az NP osztályhoz van közelebb, inkább P osztályú probléma. Minden hálózat leírható pontokkal, élekkel és ezek egymáshoz való viszonyával. Mivel a pontokat számtalan módon jeleníthetünk meg, két azonos kapcsolatokkal rendelkező gráf különböző módon jelenhet meg. Különösen akkor igaz ez, ha a gráf nagy és komplex. Ez a gráfizomorfizmus-probléma, és ezzel ezzel vissza is tértünk a kiindulóponthoz. Babai László azt állítja, hogy új algoritmusával az eddigi megoldásoknál kevesebb lépéssel jut el annak megállapításáig, hogy két gráf azonos-e. Most Eugene Luks, az Oregoni Egyetem matematikusának 1983-ban született megoldását használja a tudományos világ. Luks algoritmusában a lépések száma majdnem exponenciálisan nő, Babai algoritmusában azonban a lépések száma alig nő gyorsabban a polinominális időnél. Ez úgy hangozhat, mintha a fekete különböző árnyalatait hasonlítgatnánk össze egymással, de a szakma izgatottan reagált az eredményre. Ugyanakkor gyakorlati haszna egyelőre nem lesz a felfedezésnek. Óriási eredmény Scott Aaronson szerint azért nem lesz gyakorlati haszna, mert a most használt algoritmus is viszonylag gyorsan old meg komplex feladatokat. Babai új algoritmusa még nem ad választ arra a sejtésre, hogy NP nem egyenlő P-vel. Eddig olyan sokan próbálták megoldani a gráfizomorfizmus-problémát sikertelenül, hogy a jelenséget gráfizomorfizmus-betegségnek nevezik szakmai körökben, magyarázta az eredmény jelentőségét Ryan William, a Stanford matematikusa. Olyan ez, mintha egy agyonvizsgált elem új tulajdonságát fedeznék fel, nem emelkedik a Higgs-bozon magasságaiba a fontossága, de nagyon jelentős felfedezésről van szó. Babai László két előadásban mutatja be eredményeit, az elsőt ma mondja el a Chicagói Egyetemen, a másodikat két héttel később ugyanott. Ezek után jön az ilyenkor szokásos menet, hogy a kutatók végigrágják magukat a tanulmányon, hogy ellenőrizzék annak helyességét. Babai egyelőre nem akart beszélni a felfedezéséről, azt mondta, hogy előbb annak át kell esnie a megfelelő tudományos hitelesítési procedúrán. Megérti, hogy az internet világában egy egyszerű szemináriumi bejelentés is robbanhat, de az eredményeket előbb a tudományos közösségnek kell igazolnia. http://index.hu/tudomany/2015/11/12/grafok_arthur_kiraly_udvaraban/
