V zájmu společnosti je nalézt pravdu

 

Foto: Archiv MÚ AV ČR
Pavel Pudlák uspěl s projektem Dosažitelnost, logika a náhodnost ve výpočetní složitosti, jež spadá do disciplíny, která se v posledních letech stává významným oborem v informatice a matematice. Zkoumá matematické úlohy, které odolávají všem pokusům o vyřešení už několik desetiletí; například problém P versus NP je jedním ze sedmi matematických problémů, na jejichž vyřešení Clayův institut vypsal odměnu jeden milion amerických dolarů.

 

Skupina nositele grantu zkouší nalézt řešení problémů výpočetní složitosti pomocí metod matematické logiky. Je totiž docela možné, že důvody, proč vědci neumí na tyto otázky odpovědět, jsou fundamentálního charakteru, a proto je potřeba studovat logické aspekty těchto problémů. Prof. Pudlák se společně 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í zdůvodnit 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ěma hlavními světovými centry, která se touto tematikou zabývají.

 

Lze jej přiblížit jako otázku, zda existuje jistý „zázračný algoritmus“, jehož pomocí by se daly řešit mnohé praktické úlohy, pro které nemáme dostatečně dobré algoritmy. Například maximálně optimalizovat výrobní procesy, jízdní řády, investice a další úlohy. Algoritmus by byl užitečný i pro řešení konkrétních úloh v matematice a fyzice. Na druhou stranu by měl i velmi negativní důsledky: nebylo by možné bezpečně používat kódování tajných informací. Ten, kdo by „zázračný algoritmus“ našel jako první, by ho mohl zneužít na to, aby se dostal do jakýchkoli počítačů připojených na internet a přečetl si tajná data.

 

Jako většina matematiků, kteří se tímto problémem zabývají, věřím, že P se nerovná NP, i přesto, že neznám žádný přesvědčivý argument, že by to tak mělo být.

 

Neuvažuji, protože si myslím, že tato možnost je nepravděpodobná. Je ale pravda, že pokud by přece jenom někdo nalezl algoritmus pro NP-úplné úlohy (co neformálně nazývám zázračným algoritmem), bylo by třeba zvážit, jak tuto informaci publikovat, aby nezpůsobila paniku.

 

Vždy je v zájmu společnosti nalézt pravdu, ať už pro nás bude příznivá, nebo nepříznivá. Pokud je nepříznivá, umožní nám připravit se na její negativní důsledky. V případě důkazu P = NP je jistě lepší, když na něj přijdou čestní vědci, kteří výsledek publikují, a ne někdo, kdo se pokusí tuto znalost zneužít.

 

Kvantové počítače by skutečně v kódování způsobily revoluci, protože by byly schopné dekódovat tzv. veřejné klíče, které se v současnosti běžně používají pro mnohé účely. Nemusíme se ale obávat, protože jejich konstrukce se zdá být velice těžký fyzikálně-technický problém. Někteří vědci dokonce o reálnosti tohoto cíle pochybují. Jsem však optimista a myslím, že se to poda­ří, i když to může trvat ještě dlouho. Z hlediska teorie složitosti, i když bychom měli kvantové počítače, by byl problém P versus NP stále stejně důležitý. Zdá se totiž, že ani kvantové počítače nebudou schopny řešit všechny úlohy ze třídy NP. Od kvantových počítačů si vědci nejvíce slibují možnost simulovat kvantové fyzikální procesy, což je s klasickými počítači problém.

 

Ne víc než běžný občan – používám ho jako psací stroj a k hledání na internetu.

 

Mít plán, jak peníze využít, je základní předpoklad k získání grantu. Částka se zdá vysoká, ale je to tím, že z ní bude placen celý tým: kromě mě budou částečně placeni čtyři spolupracovníci – mj. postdoktorand a dva studenti. Naprostá většina prostředků tak bude využita na platy a odvody z platů.