Za výsledky dosažené v oblasti výpočetní složitosti byl oceněn Evropskou radou pro výzkum (ERC) prof. RNDr. Pavel Pudlák, DrSc., z Matematického ústavu AV ČR. Jako jediný z českých zástupců letos získal finanční podporu v rámci prestižní soutěže „ERC Advanced Grants“, vypsané pro zkušené výzkumné pracovníky. Uspěl s projektem „Feasibility, logic and randomness in computational complexity“ (Dosažitelnost, logika a náhodnost ve výpočetní složitosti) a po Eduardu Feireislovi (2012), Josefu Michlovi (2008), Detlefu Schröderovi (2008) a Tomáši Jungwirthovi (2011) je pátým držitelem pokročilého grantu v ČR.
Evropská rada pro výzkum z celkového počtu 2 400 přihlášených podpořila 284 projektů
částkou 660 mil. eur. Grant přidělený prof. Pudlákovi je pětiletý a činí 1 259 596 eur (cca 32
milionů korun). Prof. Pavel Pudlák je tak v krátké době druhým českým matematikem oceněným
prestižním grantem.
Výzkumná práce prof. Pavla Pudláka
Výpočetní složitost je disciplína, která má krátkou historii a teprve v poslední době začíná
být uznávaná jako důležitý obor nejen v informatice, ale i v matematice. K tomu jistě přispěl fakt,
že základní otázky v této oblasti (jako je např. známý problém „Pversus NP“) jsou matematické úlohy, které odolávají všem pokusům o vyřešení už několik
desetiletí. Skupina vedená prof. Pudlákem se je snaží řešit pomocí metod matematické logiky. Jak se
prof. Pudlák domnívá, je docela možné, že důvody proč neumíme na tyto otázky odpovědět, jsou
fundamentálního charakteru, a proto je potřeba studovat logické aspekty těchto problémů. Z tohoto
důvodu se spolu se svými spolupracovníky zaměřil na oblast na pomezí matematické logiky a teorie
složitosti, která se nazývá důkazová složitost. Zatímco výpočetní složitost se zabývá otázkami, jak
je obtížné něco vypočítat, důkazová složitost si klade otázky, jak je obtížné něco dokázat. Metody
důkazové složitosti umožňují dokázat jak teoretické výsledky (např. obtížnost některých
matematických problémů), tak i více praktické – například, že určitou výpočetní úlohu nelze řešit
jistým typem algoritmů. Pražská skupina spolu se skupinou prof. Stephena Cooka v Torontu jsou dvě
hlavní světová centra, která se touto tematikou zabývají.
Prof. Pavel Pudlák o „P versus NP“
Náš výzkum je motivován jedním důležitým problémem, který se nazývá problém „P versus NP“. Pro
laiky se dá tento problém vysvětlit jako otázka, zda existuje jistý „zázračný algoritmus“. Pomocí
tohoto algoritmu by se daly řešit mnohé praktické úlohy, pro které nemáme dostatečně dobré
algoritmy. Například by se daly maximálně optimalizovat výrobní procesy, jízdní řády, investice a
další úlohy. Algoritmus by byl samozřejmě velmi užitečný i pro řešení konkrétních úloh v matematice
a fyzice. Na druhou stranu by takový algoritmus měl i velmi negativní důsledky: nebylo by možné
bezpečně používat kódovaní tajných informací. Ten, kdo by tento zázračný algoritmus našel jako
první, by ho mohl zneužít na to, aby se dostal do jakýchkoliv počítačů připojených na internet a
přečetl si tajná
data.
Toto je pochopitelně poněkud zjednodušený popis matematického problému, ale za jistých okolností
(pokud by konstanty skryté ve formulaci problému byly malé) by popsaná situace mohla nastat. Pro
zajímavost se ještě zmiňme, že „P versus NP“ je jeden ze sedmi matematických problémů, na jejichž
vyřešení Clayův institut vypsal odměnu 1 milion amerických dolarů.
Většina vědců, která se zabývá touto oblastí teoretické informatiky, se domnívá, že P se nerovná
NP, a tedy že zázračný algoritmus neexistuje. Dosud ale nebyly vyvinuty metody, které by umožňovaly
něco takového dokázat. Naše skupina se zaměřila na přístup založený na matematické logice. Snažíme
se hledat souvislosti mezi problémy jak něco dostatečně rychle vypočítat a problémy jak něco
dokázat krátkým důkazem. Jinými slovy, hledáme souvislosti mezi výpočetní složitostí a důkazovou
složitostí. Ukazuje se, že tyto dva typy složitosti jsou jenom dva různé pohledy na obecný fenomén
složitosti.
Kontakt:
Prof. RNDr. Pavel Pudlák, DrSc., Matematický ústav AV ČR, tel.: +420 222 090 721, e-mail:
pudlak@math.cas.cz
Připravil: Odbor mediální komunikace Kanceláře AV ČR
1.10.2013
