Matfyzácká stopa v oceněném výzkumu
Churchovu cenu, jedno z nejvýznamnějších ocenění v teoretické informatice, letos získala dvojice vědců, jejichž teorii se podařilo potvrdit i díky poznatkům Libora Barto z Katedry algebry.
Laureáty prestižní Alonzo Church Award se v dubnu stali matematik Tomás Feder ze Stanford University a informatik Moshe Vardi z Rice University v Houstonu. Téma jejich výzkumu souvisí se slavným problémem P vs. NP o složitosti vyhledávacích problémů.
Zjednodušeně zní otázka následovně: Pokud umíme pro daný problém efektivně ověřit, že je daná odpověď správná (tzv. NP-problém), je také možné odpověď efektivně najít (tzv. P-problém)? V 70. letech bylo dokázáno, že existují „nejsložitější“ vyhledávací problémy, a pokud tyto nejsou efektivně řešitelné, pak existuje nekonečná škála složitosti mezi P-problémy a těmito nejsložitějšími NP-problémy.
Ukazuje se, že řada přirozených vyhledávacích problémů je řešitelná buď efektivně, anebo patří mezi ty nejsložitější. Feder a Vardi zjišťovali, které typy problémů vykazují tuto dichotomii, a před 25 lety předpověděli, že takovou vlastnost mají tzv. problémy omezujících podmínek (CSP). Jejich domněnka vyvolala značný zájem mezi matematiky i informatiky. Některé speciální případy byly v té době již potvrzeny – jeden z nejslavnějších výsledků, který přinesli matematici Jaroslav Nešetřil a Pavol Hell, se týkal existence homomorfismů do daného grafu.
Postupem času byla nalezena zásadní souvislost mezi složitostí daného problému a jistým typem symetrie, který vykazuje, a do hry vstoupila algebra. Libor Barto z Katedry algebry MFF UK společně s Marcinem Kozikem z Jagellonské univerzity v polském Krakově v roce 2009 popsali pomocí těchto symetrií právě ty problémy, které jsou efektivně řešitelné vylučovací metodou.
Jiná skupina matematiků podobně klasifikovala problémy, které jsou efektivně řešitelné pomocí úprav podobného typu, jako když řešíme soustavy lineárních rovnic. Snaha algebraiků byla završena v loňském roce, kdy Federovu a Vardiho domněnku nezávisle na sobě potvrdili Andrej Bulatov ze Simon Fraser University a Dmitrij Zhuk z Moskevské státní univerzity. Jejich řešení kombinuje oba výše zmíněné algoritmy. Práce tak podává univerzální algoritmus, který řeší všechny efektivně řešitelné problémy CSP.
Zmíněný Dmitrij Zhuk nastupuje od září na Katedru algebry MFF UK jako nový člen výzkumné skupiny Libora Barto. V rámci výzkumu, na který Barto získal koncem loňského roku grant od Evropské výzkumné rady, budou vědci pracovat na zobecnění výsledků pro další úlohy. „Společně budeme bádat nad zobecněním těchto výsledků tak, aby zahrnovaly například aproximační úlohy či vyhledávání mezi nekonečně mnoha možnostmi. Cílem je identifikovat, jaké typy symetrie odlišují složité problémy od jednoduchých, a tím se trochu přiblížit vyřešení problému P vs. NP,“ říká Barto.
