Nejvyšší medaili Akademie věd převzal světově uznávaný matematik Pavel Pudlák

Pavel Pudlák z Matematického ústavu AV ČR se zabývá logikou a výpočetní složitostí. Patří k nejcitovanějším českým matematikům, vydal několik monografií, je nositelem Ceny Neuron a v roce 2013 získal prestižní evropský ERC Advanced grant, který z Česka obdržela zatím jen hrstka vědců. Za celoživotní práci mu Akademie věd v pondělí 27. června 2022 udělila čestnou medaili De scientia et humanitate optime meritis.

Pavel Pudlák se zabývá teorií složitosti. Zda je, nebo není nějaká matematická úloha těžká, má velký význam nejen pro matematiky, ale pro každého z nás. Má to totiž praktický dopad na kryptografii neboli šifrování.

Soudobé šifrování se zakládá na jednoduchém, ale účinném principu: součin dvou velkých čísel lze snadno vypočítat, naopak rozklad velkého čísla jednoduchý není. Vynásobit dvě prvočísla o 70 číslicích současné počítače hravě zvládnou. Obráceně to však nefunguje.

Dostanete-li počítač číslo o 140 cifrách s informací, že je součinem dvou prvočísel, najít tato dvě čísla je úkolem na hranici možností i pro ty nejvýkonnější z nich. Toho využívá kryptografie. Když totiž jeden z dvojice drží „klíč“, tedy jedno z prvočísel, z nichž se velké číslo skládá, dokáže hravě číslo rozložit na dvě. Bez tohoto prvočísla (klíče) jde ale o složitou úlohu. Jenže vědcům se nedaří matematicky dokázat, že to opravdu složité je. Tomu se věnuje jeden z problémů milénia nazvaný „P versus NP“.

Jde o jednu ze sedmi největších výzev moderní matematiky vyhlášených v roce 2000 Clayovým matematickým institutem, ze kterých byla dosud vyřešena pouze jediná. Pavel Pudlák se jí přitom věnoval ještě dříve, než byla vyhlášena.

Pavel Pudlák z Matematického ústavu AV ČR se zabývá logikou a výpočetní složitostí.

Různé úrovně složitosti
P a NP jsou takzvané třídy složitosti neboli množiny matematických úloh. Zatímco do P patří úlohy, které lze vyřešit „v rozumném čase“, do NP náležejí nad rámec toho ještě další úlohy, jež prostým zkoušením možností v reálném čase řešitelné nejsou – třeba právě rozklad velkých čísel. Jde o úkol, u nějž jednoduchý algoritmus řešení nenalezne. Nicméně pokud člověk dostane nějaký návrh na výsledek, dokáže snadno ověřit, zda je, nebo není správným řešením.

Z problému milénia vyplývá otázka, zda pro všechny úlohy existuje rychlý algoritmus řešení. Jsou jen dvě možnosti. Buď existuje vždy (což je třeba dokázat), a tedy P = NP, nebo existuje aspoň jedna úloha, pro kterou rychlý algoritmus neexistuje, a musíme se smířit s tím, že prostě navždy složitou úlohou zůstane. Vědci se spíše přiklánějí k variantě, že P a NP si rovny nejsou, jinými slovy, že těžké úlohy zkrátka existují. Jen to zatím nedovedou dokázat. Na toho, komu se to povede, čeká milion dolarů.

Otřese se současný systém šifrování v základech?

Důsledky takového úspěchu budou přínosné zejména pro matematiku samu… a uklidní kryptografy, že je jejich šifrování bezpečné. Naopak pokud by se prokázalo, že P je rovno NP (tedy, že všechny úlohy jsou řešitelné v reálném čase), současný systém šifrování by se otřásl v základech.

„Může se ale stát, že ačkoli se P nerovná NP, zrovna právě úloha rozkladu velkých čísel těžká není (patří do P) a systémy veřejných klíčů bezpečné nejsou,“ řekl Pavel Pudlák v rozhovoru pro časopis Akademie věd A / Věda a výzkum. Naopak třeba existuje aspoň jedna jiná složitá úloha, kterou řešit neumíme.

Kryptografové tedy asi mohou zůstat ještě dlouho v klidu. Zato matematici ne – někteří tvrdí, že P vs. NP je ze zbývajících problémů milénia nejtěžší. „Mezi odborníky jsou skeptici, kteří jsou přesvědčeni, že vyřešení nedosáhneme ani za dvě stě let. Když se ale podívám, co se podařilo ve 20. a 21. století, jsem přesvědčený, že tak beznadějné to není. Zatím k tomu ovšem blízko nemáme,“ přiznal Pavel Pudlák.

Se svou skupinou přidává do skládačky další dílky. Studují speciální případy úloh a hledají meze současných metod v dokazování dolních odhadů složitosti – spodních mezí času, pod kterou daná úloha určitě řešit nejde. „Doufáme, že díky novým myšlenkám, které se při řešení speciálních případů objeví, nasbíráme spoustu metod, pomocí nichž vyřešíme nakonec i fundamentální problém,“ vysvětlil přístup teoretických matematiků Pavel Pudlák.

Více o Pavlu Pudlákovi se dočtete také v časopise A / Věda a výzkum, který vydává Akademie věd ČR. Všechna dosavadní čísla jsou k dispozici zdarma na našem webu.

Text: Viktor Černoch, Divize vnějších vztahů SSČ AV ČR
Foto: Pavlína Jáchimová, Divize vnějších vztahů SSČ AV ČR, fotografie v galerii Miroslav Rozložník, Matematický ústav AV ČR
Text i fotografie jsou uvolněny pod svobodnou licencí Creative Commons.

Přečtěte si také

• Tomáš Čižmár převzal Cenu ministra školství, mládeže a tělovýchovy
• Nadějní středoškoláci prezentovali vědecké projekty na konferenci Otevřené vědy
• Technologická agentura ocenila aplikované výzkumy pracovišť Akademie věd
• Česká a Saská akademie věd chtějí rozvíjet spolupráci na důležitých tématech
• ERC Synergy grant podpoří výzkum Ondřeje Nováka z Akademie věd ČR
• Podpora mladých vědců je důležitá, shodují se účastníci Wichterleho kempu
• Akademie věd podpořila prémiemi tři zkušené badatele a šest nadějí
• Výstava Věda fotogenická se představuje v Poslanecké sněmovně
• Akademie věd představila výsledky tří výzkumných programů Strategie AV21
• Týden Akademie věd je nářez, ale těšíme se na něj, říkají popularizátoři