Barto zkoumá výpočetní problémy, má druhý ERC grant

Jaké výpočetní problémy jdou efektivně řešit, a které už ne? Odpovědi na tuto fundamentální otázku informatiky bude v rámci prestižního ERC Synergy grantu hledat Libor Barto z Matematicko-fyzikální fakulty UK. Zajímá se o univerzální efektivní algoritmy i univerzální důvody pro nemožnost efektivního řešení, na čemž bude díky štědré podpoře zhruba osmi milionů eur pracovat spolu s kolegy z univerzit ve Vídni a Drážďanech. Výsledky jejich bádání mohou přispět i k vyřešení jednoho z „milionových problémů matematiky“.

„Matematika je plná problémů! V rámci nového ERC projektu se budeme snažit lépe pochopit složitost výpočtů. Chceme vědět, které problémy se dají na počítači řešit rychle a které ne,“ popisuje Libor Barto z Matematicko-fyzikální fakulty UK, jeden ze spoluřešitelů nového prestižního grantu Evropské výzkumné rady (ERC).

Jak si takový výpočetní problém představit? „To je nějaká úloha pro počítač, která má jasně dané vstupy a výstupy. Výpočetní problémy jsou v dnešní společnosti všudypřítomné, řeší se například při přenosu a šifrování dat, při návrhu a optimalizaci logistiky, při vyhledávání stránek na internetu, nebo při analýze dat. Jednoduchým výpočetním problémem je například násobení čísel. Na vstupu máme dvě čísla a na výstupu požadujeme jejich součin. I když budeme násobit mnohaciferná čísla, tak to pro počítač bude jednoduché a i naivní algoritmus násobení ‚pod sebe‘, který mimochodem není nejefektivnější, dokáže tento problém vyřešit přibližně v ‚n na druhou‘ krocích, kde n je celkový počet cifer vstupních čísel. Ale pak tu jsou problémy, které neumíme obecně řešit ani v ‚n na bilion‘ krocích. Například kdybychom měli skupinu n lidí a chtěli je rozdělit do tří skupin tak, aby v žádné skupině nebyli nepřátelé. To je i pro počítač výzva. Naivní algoritmus, který systematicky prozkoumá všechny možnosti, potřebuje v nejhorším případě ‚tři na n‘ možností, což je už pro docela malá n, třeba n=100, astronomicky velké číslo. Žádný podstatně lepší algoritmus na tento problém neznáme a myslíme si, že neexistuje. Na potvrzení nebo vyvrácení této domněnky vypsal Clayův matematický institut odměnu milion dolarů, je to jeden z takzvaných problémů tisíciletí. Jedním z cílů grantu je lépe pochopit, kde je hranice mezi efektivně řešitelnými a neřešitelnými problémy, čímž snad také přispějeme k vyřešení zmíněného milionového problému.“ 

Spolupráce vyzkoušena a funguje

Nový ERC grant s akronynem POCOCOP (POlynomial – time COmputation: opening the blackboxes in COnstraint Problems) je z kategorie Synergy, to znamená, že se na řešení projektu podílí skupina několika hlavních řešitelů. „Spolu s Manuelem Bodirskym z Drážďan a Michaelem Pinskerem z Vídně se známe dlouho, máme i nějaké společné články a chtěli jsme naši spolupráci posunout na další úroveň – vytvořit z našich skupin jeden velký tým,“ popisuje třetí hlavní řešitel z Matfyzu UK.

„Samotná volba tématu vyplývá z toho, co děláme – každý z nás se specializuje na trochu jiný směr, společně ale pokrýváme široký záběr matematiky a teoretické informatiky, což může přinést ten klíčový posun v celé problematice,“ říká Libor Barto.

„Vycházíme z třídy problémů, která se označuje CSP – česky by to bylo problém splnitelnosti omezujících podmínek nad konečnými obory, a ten budeme rozšiřovat ve třech směrech: Jedním směrem je aproximace – hledat přibližné řešení, což může problém zjednodušit. V našem příkladu bychom se třeba mohli snažit lidi rozdělit na deset skupin, i když víme, že dělení na tři skupiny existuje. Druhým směrem je optimalizace – hledat ideální řešení, v našem příkladu, aby co nejméně nepřátel bylo spolu. Třetí směr je k nekonečným oborům, kde řešením problému jsou třeba čísla – příkladem je řešení soustav lineárních rovnic nebo nerovnic. Pro úspěch bude klíčové, abychom vzájemně pronikly do všech směrů, porozuměli jim do větší hloubky a dokázali je propojit,“ říká Barto, který dodává, že při psaní grantové žádosti vyzkoušeli, že spolupráce bude fungovat. „Každý z nás přispěl a přinesl originální myšlenky. Výsledná žádost je daleko lepší, než jakou by byl schopen vytvořit kdokoliv z nás.“

Unikátní výsledky, které mohou změnit celý obor

O ERC grantech se říká, že mají unikátní myšlenku, která když se podaří realizovat, může způsobit průlom celého oboru. „Pokud náš projekt vyjde, tak bychom mohli pochopit výpočetní složitost na zcela nové úrovni porozumění, než jsme měli doposud. V současnosti jsou často výpočetní problémy zkoumány separátně – pro konkrétní problém se hledá efektivní algoritmus nebo argument, že takový algoritmus neexistuje. My vytvoříme obecnější teorii, která objasní, proč je některý problém lehký a jiný těžký. Ve výsledku by to mohl být dokonce nějaký algoritmus, kterému když popíšeme daný problém, tak nám téměř automaticky vyhodnotí, zda řešení problému spadá do lehké či složité kategorie,“ vysvětluje Barto, pro kterého je to již druhý ERC grant.

Jak dopadl ten první? „Do konce ledna ještě stále probíhá! Ale myslím, že už teď můžeme říci, že dopadl dobře – jak to u teoretických grantů bývá, tak mnoho z těch konkrétních otázek, co jsem si na začátku pokládal, se vyvinulo jiným směrem, jiné otázky přibyly. Získané výsledky ale například umožnily vznik tohoto druhého ERC projektu, bez nich by to vůbec nebylo možné,“ říká Libor Barto, podle kterého je matematika nejkrásnější a nejkreativnější obor lidské činnosti. „Jako nematematik můžete malovat nebo skládat symfonie, ale oproti matematice je to stále ještě nic. Není nic krásnějšího, než když řešíte nějaký složitý matematický problém a najednou se to povede, vše do sebe zapadne a vy máte řešení.“

Pokud by vás výzkumné téma výpočetních složitostí zajímalo více, doporučujeme nedávný článek Libora Barto v časopise Vesmír.