Matematik Libor Barto získal ERC grant

1. prosince 2017

Doc. Libor Barto z katedry algebry MFF UK získal prestižní grant Evropské výzkumné rady (ERC). Jeho výzkum by měl přispět k vyřešení zásadních otázek z oblasti výpočetní složitosti.

Rozvoj pětiletého výzkumného projektu Symmetry in Computational Complexity podpoří „konsolidační“ grant v částce převyšující jeden milion eur. Ten by měl umožnit nejen realizaci samotného výzkumu, ale také vytvoření vlastního výzkumného týmu: „Členy týmu budu teprve vybírat. Plán je mít tři doktorandy a tři postdoky.“

Podpořený výzkum spadá do oblasti výpočetní složitosti, což je obor teoretické informatiky, který zkoumá, kolik času nebo prostoru je potřeba k vyřešení výpočetního problému v závislosti na velikosti vstupních dat. „Pro jistou skupinu výpočetních problémů se ukázalo, že složitost je určená tím, jak je daný problém symetrický, v určitém přesném technickém smyslu. Mám vizi, že symetrie bude v budoucnu organizujícím principem celé výpočetní složitosti,“ přibližuje doc. Barto výchozí teze svého projektu.

Výzkumný projekt kombinuje přístupy několika matematických disciplín, jako je algebra, analýza, logika a kombinatorika. Ve výsledku by pak měl pomoci sjednotit teorii výpočetní složitosti a vyřešit její zásadní problémy, mezi které patří tzv. „Unique Games Conjecture” nebo slavný problém „P versus NP”. „Jde o základní výzkum, tedy hlavní motivací je něčemu lépe porozumět, nikoliv vyřešit nějaký praktický problém. Porozumění často vede i k praktickým aplikacím, ale to může být ještě dlouhá cesta,“ uzavírá doc. Barto.

OMK, foto Eva Kořínková