(dolgoztam ezen a címen egy kicsit)
Babai László idén novemberben egy háromrészes chicago-i előadássorozatban jelentette be, hogy kvázipolinomiális algoritmust talált a gráfizomorfizmus problémára. Tegnap kora délelőttől késő estéig (nem tudom, hogy pontosan meddig, én az előadás ún.központi részén voltam csak ott, amikor a Vígszínházban szünet volt, akkor beszéltem valakivel telefonon, hogy még tart az előadás). beszélt a Rényi Intézetben, ami teljesen elképesztő.
A gráfizomorfizmus probléma megoldásáról az Index is címlapon számolt be, azóta a kézirat is nyilvánossá vált. Nagyjából arról van szó, hogy van egy tetszőlegesen bonyolult szerkezetű n darabkából álló általánosított Rubik-kocka és el kellene dönteni exp(polylog(n)) időben azt, hogy egy bizonyos állapotból elérhető-e egy bizonyos másik állapot. Nem várható, hogy a probléma polinomiális időben legyen megoldható, mert két szorzótáblájával adott azonos méretű véges csoport izomorfiájának (ez egy könnyebb probléma) megoldására stabilan és teljesen reménytelenül egy merev kvázipolinomiális határ van (a logaritmikus szorzó konstanst nem sikerült 37 éve 1-ről 0.9999999-re vinni). A gráfizomorfizmus probléma Babai-féle megoldása nagyon bőven az április tréfa kategóriában volt, olyan jellegű áttörés, amire senki sem számított, és még mindig meg vannak döbbenve a komplexitás-elmélészek.
Ez az egész úgy világraszóló eredmény, ahogy van, nem nagyon tudnám, és nem is nagyon akarom hasonlítgatni más dolgokhoz, de kicsit talán egy 9 méteres távolugrásra vagy egy 9.5-ös száz síkra emlékeztet, elvileg képes lehet rá egy ember, gyakorlatilag elég nehéz elképzelni.
Babai rögtön azzal kezdte az előadását, hogy a bizonyítás még nincs ellenőrizve, és tegnap hosszú órákat töltött azzal, hogy megteremtse annak lehetőségét, hogy az esetleges hibát megtalálják. Ezt is elég nehéz elmagyarázni a matematika határain kívül.
Nincs szó alkalmazhatóságról, nincs olyan valódi világbeli probléma, ami most majd gyorsabban lesz megoldható, ez egy Mount Everest, és azért kell megmászni, mert ott van.
Egy egészen más Magyarország volt ott tegnap a Rényiben, mint amiről sírdogálni szoktunk ezen a blogon. Van ennek az országnak néhány nagyon vonzó arca, és a magyar kombinatorika-számítástudomány a határterületeivel együtt ezen nagyon vonzó arcok közé tartozik, ez az a része a nemzeti kultúránknak, amelyik messze-messze az európai élvonalhoz tartozik. És nem, nem lesz vörös farok, áthallás, nem nagyon szeretnék ilyesmit, tegnap olyan jó volt kicsinek lenni egy sarokban. Nem kell túlmagyarázni.
