Oficiální časopis Akademie věd ČR

 


Z monitoringu tisku

 

Akademický bulletin 2010–2015

Plakat_obalky_web.jpg



Stopy AB v jiných titulech

Stopa AB v dalších médiích a knižních titulech

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

Prestižní grant Evropské rady pro výzkum (European Research Council – ERC) získal letos jako jediný český vědec prof. Pavel Pudlák z Matematického ústavu AV ČR. Rada jej ocenila za výsledky, jichž dosáhl v oblasti výpočetní složitosti. 
 
12_1.jpg
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í.
 
Pane profesore, můžete prosím objasnit problém P versus NP laikovi?
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.
 
Přikláníte se k existenci rovnosti P a NP, anebo předpokládáte nerovnost?
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.
 
Uvažujete při své práci o důsledcích případného důkazu P = NP?
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.
 
Vezmeme-li v potaz např. jen to, že bezpečnost internetového bankovnictví je založená na nerovnosti P a NP, je vůbec v zájmu společnosti dospět k důkazu, případně rovnosti?
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.
 
Podle mnohých budou revoluci v kódování a dekódování algoritmů představovat kvantové počítače. Jak se díváte na konstrukci takového počítače a jeho význam při řešení této úlohy?
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.
 
Do jaké míry při výzkumu využíváte počítač vy?
Ne víc než běžný občan – používám ho jako psací stroj a k hledání na internetu.
 
Grant Evropské rady pro výzkum činí téměř 30 milionů, jak s nimi naložíte?
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ů.      
 
GABRIELA ADÁMKOVÁ