Gráfok izomorfizmusa
http://index.hu/tudomany/2015/11/12/grafok_arthur_kiraly_udvaraban/
2015.11.12. "Szenzációs magyar felfedezés forgatja fel a matematikát" olvashattuk a híradásokban
Mi is ennek a felfedezésnek a lényege?
Egy magyar kutató, a Chicagói Egyetemen tanító Babai László egy régi problémára, a gráfizomorfizmus-problémára (leegyszerűsítve: két gráf azonos-e) olyan új algoritmust alkotott, amely az eddigi megoldásoknál kevesebb lépéssel jut el a megoldásig.
Most Eugene Luks megoldását használja a tudományos világ, algoritmusában a lépések száma majdnem exponenciálisan nő, Babai László algoritmusában azonban a lépések száma alig nő gyorsabban a polinominális időnél.