Harminc év munkája érett be

Babai László

A korábbinál sokkal kedvezőbb időkorláttal rendelkező algoritmust talált egy nevezetes számítási feladatra, a gráfizomorfizmus-problémára Babai László akadémikus, a Chicagói Egyetem tanára. A matematikusok által nagy érdeklődéssel és izgalommal fogadott hír tudományos hátterét Rónyai Lajos akadémikus foglalta össze az mta.hu számára – az IT café ezt a cikket közli most változatlan formában.

Az elmúlt hetekben szárnyra kapott a hír a számításelmélet iránt érdeklődők körében: Babai László professzor áttörést jelentő eredményt ért el egy nevezetes számítási feladattal, a gráfizomorfizmus-problémával (röviden GI) kapcsolatban.

Mi is ez a feladat, és mi teszi kiemelten fontossá?

A feladat bemenete két véges hálózat, G és H, mindkettő csomópontokból és köztük levő kapcsolatokból, szokásosabb nevükön élekből áll. El kell dönteni, hogy a két hálózat izomorf-e. Az izomorfia azt jelenti, hogy G csomópontjait kölcsönösen egyértelműen megfeleltethetjük H csomópontjainak úgy, hogy ez a megfeleltetés megtartja a kapcsolatokat és azok hiányát is. Ha két G-beli csomópont között van kapcsolat (él), akkor a nekik megfelelő H-beli pontpár között is van. Ha pedig a két G-beli csomópont között nincs él, akkor a H-beli megfelelőik között sincs.

A következő ábrán három hálózat látható, mindegyiknek négy csomópontja van. Az első kettő izomorf egymással, egy lehetséges megfeleltetés 1 ↔ a, 2 ↔ b, 3 ↔ c, 4 ↔ d. Az első és a harmadik hálózat viszont nem izomorf egymással: az elsőnek négy éle van, a harmadiknak pedig öt.

Az izomorfia a matematika számos területének alapfogalma, így eldöntésének a nehézsége a számításelmélet egyik – több mint 40 éve felismert - alapproblémája. A GI e problémaosztály alapmodellje. Más véges struktúrák izomorfizmusproblémája visszavezethető a GI-feladatra.

Ezzel egyenértékű kérdés a struktúrák szimmetriáinak felismerése, ami ugyancsak több matematikai terület központi kérdése.

A gyakorlatban is felbukkan a GI-feladat kémiai hálózatok (ahol a csomópontok atomok, a kapcsolatok kémiai kötések) és elektronikus áramkörök (a csomópontok áramköri elemek, a kapcsolatok összeköttetések) elemzése során.

Ki kell emelnünk, hogy Babai László új algoritmusa (ha helyessége bebizonyosodik) elméleti téren jelent áttörést; a gyakorlatban felmerülő gráfokra régóta ismeretesek hatékony programok (Brendan McKay és Adolfo Piperno módszerei). Ezeknél azonban nincs elméleti garancia arra, hogy minden esetben hatékonyan működnek. Az ilyen elméleti garanciák keresése a számítástudomány központi törekvése.

A cikk még nem ért véget, kérlek, lapozz!