A gráfizomorfizmust ismét legyőzték

Fájdalmas volt az elmúlt pár hét az elméleti számítástechnológia kutatóinak. Január 4.-én a magyar származású Babai László, aki a Chicagói Egyetem professzora, sokkolta a tudományos közösséget azzal hogy visszavonta a még 2015 novemberi állítását, amit a az elméleti számítástechnológia kutatói az évtized előrelépéseként tartottak számon. Azonban Babai már január 9-re előállt a hiba megoldásával. És most a hibát megtaláló matematikus – Harald Helfgott a német Göttingen Egyetem és a francia Tudományos Kutatásért Nemzeti Központ kutatója – is nyíltan elismert, a Párizsban tartott Bourbaki szemináriumon, ami a matematika egyik legkiemelkedőbb előadás sorozata.

A gráfizomorfizmus azt a problémát feszegeti, hogy mikor rendelkezik két eltérő kinézetű gráf – pontok és élek hálója- ugyanazokkal az alapvető kapcsolatokkal. Annak ellenére hogy a probléma igen egyszerűnek hangzik az elméleti számítástechnológia kutatói már több mint 30 éve küzdenek a problémával hogy van e olyan algoritmus ami képes hatékonyan megoldani a gráfizomorfizmus.

Babai eredményei egy olyan algoritmust mutatnak be, ami képes a jelenséget „kvázi-polinom” időn belül megoldani. Egyszerűbben fogalmazva az algoritmus a gráfizomorfizmus problémáját majdnem teljesen átviszi a hatékonyan nem megoldható és a megoldható problémák között lévő öblön – most már a hatékonyan megoldható problémák partján lubickol, amiknek a lefutási idejét a számítástechnikában „polinomnak” nevezik.

A Bourbaki szemináriumra készülve, Helfgott több hónapot töltött Babai algoritmusának a tanulmányozásával. És ahogy az algoritmust vizsgálta, rájött, hogy van egy apró hiba „Split-or-Johnson” folyamat nevű lépésnél. Ez a folyamat hivatott leegyszerűsíteni a gráfizomorfizmus problémáját, azzal hogy vagy azonosítja a kisebb „Johnson” gráfot a két vizsgált gráf közül, vagy valami módot talál, hogy a gráfok szimmetriájának megfelelően színezze be azokat, ezzel könnyebé téve a két struktúra összehasonlítását.

A Split-or-Johnson folyamat magába foglalt egy visszatérő lépést, aminél egy szubrutin felosztja a problémát két kisebb részre és visszahívja magát, hogy fusson le ismét a kisebb részeken. De minden alkalommal amikor ez a szubrutin lefut, hamis tényezők kerülnek abba hogy a színezés hogyan is mutatja meg a szimmetriát, és ezek a hibák irányíthatatlanul felhalmozódhatnak. „A folyamatnál aminél a hibák száma ilyen módon növekszik az elágazásokhoz való visszatérése teljesen katasztrofális” írta Helfgott az emailjében.

Babainak sikerült rájönnie, hogy a szubrutin hogyan hívhatja vissza magát anélkül, hogy két ágra oszlana minden lépésnél. „Biztos vagyok benne, hogy a  javítás helyes,” közölte Helfgott.

Babai most a tanulmány újradolgozásán munkálkodik, amiben már ez az új javítás és több másik korábbi módosítás is bekerül, amik más az előző években felhalmozott hozzászólások nyomán jöttek létre. És reményei szerint a vázlatot egy hónapon belül közzéteheti.

Forrás: www.quantamagazine.org

Szerkesztő: arsratio

Oszd meg

Hozzászólás küldése

Az email címet nem tesszük közzé. A kötelező mezőket * karakterrel jelöljük.

A honlap további használatához a sütik használatát el kell fogadni. További információ

A süti beállítások ennél a honlapnál engedélyezett a legjobb felhasználói élmény érdekében. Amennyiben a beállítás változtatása nélkül kerül sor a honlap használatára, vagy az "Elfogadás" gombra történik kattintás, azzal a felhasználó elfogadja a sütik használatát.

Bezárás