Rozluštil záhadu, získal Gödelovu cenu a bádá na Karlovce

Třicet let, již od roku 1993, se každoročně uděluje Gödelova cena za nejlepší odborné články z oblasti teoretické informatiky, jméno nese po rakouském matematikovi Kurtovi Gödelovi. Letos patří mezi laureáty též Hans Raj Tiwary z katedry aplikované matematiky Matematicko-fyzikální fakulty Univerzity Karlovy. Oceněn byl za práci, jíž napsal společně se zahraničními kolegy z Nizozemska, Německa a Belgie.

„Na střední škole jsem chtěl studovat matematiku či fyziku a člověk sní, že by jednou dostal nobelovku nebo tak něco,“ říká Hans Raj Tiwary.

Předně vám velmi gratuluji k získání prestižní Gödelovy ceny! Jak jste se o tomto ocenění dozvěděl?

Je to trochu kuriózní příběh. Komise, která ocenění vyhlašuje, sídlí v USA. To znamená, že je tam časový posun. A tu noc jsem spal v jednom pokoji se svými dětmi a moje dcera se kolem půlnoci vzbudila a měla nějaký z těch dětských jakoby nepodstatných požadavků; možná to znáte. Trochu mě to rozladilo a po tom, co jsem ji znovu uspal, jsem už nemohl usnout. Takže jsem si šel dát sklenku mléka, otevřel e-mail a našel zprávu: „Gratulujeme, ještě to není oficiálně oznámeno, ale získáváte Gödelovu cenu!“

To se stalo v jednu hodinu ráno a pak už jsem nemohl usnout vůbec, protože to bylo tak vzrušující a nečekané... Když se mě pak žena ráno zeptala: „Jak ses vyspal?“ Musel jsem odpovědět: „Spal jsem hodinu, protože jsem čekal, až ti řeknu, proč už nemůžu spát...“ Byl to šok, protože je to prestižní ocenění a vlastně je pořád trochu těžké tomu uvěřit.

Bylo toto ocenění vaším snem?

Možná když mi bylo dvanáct nebo čtrnáct. Na střední škole jsem chtěl studovat matematiku nebo fyziku a v té době člověk samozřejmě sní o tom, že by jednou dostal Nobelovu cenu nebo něco podobného. Ale pak jsem přešel na informatiku a ekvivalentem Nobelovky v informatice by byla Turingova cena. Takže v počátku máte takové fantazie, ale postupně se z toho stanou jen dětské sny. Člověk vyroste a uvědomí si, že to jsou tak výjimečné věci, že s nimi nemůže normálně počítat, a začne se soustředit na to, aby dělal dobrou vědu, protože ho to baví. Takže bych neřekl, že to byl můj sen. Ale ne v tom smyslu, že bych to nechtěl, jen to není váš důvod, proč děláte informatiku.

Jaká byla reakce vašich kolegů? Překvapilo vás něco?

Reakce byly celkem  očekávatelné. Zpočátku jsem o tom nesměl nikomu říct, což bylo těžké, poněvadž jsem tu radost chtěl sdílet. Když to pak bylo oficiálně oznámeno, začali mi kolegové posílat gratulace, někdo to viděl na stránce s oznámením a poslal e-mail celému oddělení. Na což mi napsalo ještě více lidí, až jsem z toho byl nesvůj.

Slavnostní ceremoniál se uskuteční na 55^th Symposium on Theory of Computing (STOC), které se bude konat příští týden v Orlandu na Floridě. Těšíte se na něj?

Ano, ale bohužel se tam osobně nepodívám. Tato cena se obvykle uděluje na jedné ze dvou konferencí buď na STOC, anebo na ICALP, což je evropská verze. A letos se bude udělovat na STOC ve Spojených státech. A v době, kdy jsem dostal oznámení, už bylo pozdě zařizovat víza a další věci.

Cena se uděluje za výzkumnou publikaci. Tušíte, proč komise ocenila právě tuto práci? V čem spočívá její jedinečnost? 

Tato práce, kterou jsem napsal společně se čtyřmi kolegy z Nizozemska, Německa a Belgie, se od počátku těšila velké pozornosti. Hned když jsme výsledek dokázali, byli jsme si celkem jistí, že jde o dobrý výsledek – vyřešili jsme dvacet let starý problém! Poslali jsme ho na STOC, což je taková jedna ze dvou nejlepších konferencí v oblasti počítačových věd a obvykle už jen přijetí článku je velkou poctou. A náš příspěvek byl v tom samém roce nominován na cenu Best Paper Award. Lidé z něj byli nadšení, takže nebylo až tak překvapivé, že se mu dostává velké pozornosti. Například loni tento článek dostal další STOC cenu Test of Time. I když byla práce publikována před deseti lety, stále inspiruje k dalším výzkumům, čas ji prověřil. Takže v tomto smyslu to nebylo zcela šokující, ale samozřejmě to nelze ani předvídat.

Hans Raj Tiwary působí na Univerzitě Karlově, kde je i tato IT laboratoř Rotunda v malostranské budově MFF UK, již deset let.

Oceněná publikace se týká kombinatorické optimalizace. Můžete pro nás laiky vysvětlit hlavní myšlenku? 

Jedním ze základních problémů, jimiž se v informatice zabýváme, je, jak přimět počítače řešit problémy. Základní přístup spočívá v tom, že je rozdělíte na sérii kroků, které počítač přesně dodržuje. Tomu se říká algoritmus – postup řešení. A největším otevřeným problémem, o kterém si někteří lidé myslí, že ani není řešitelný, je, jaké problémy můžeme počítačům říct, aby řešily rychle. Existují problémy, které jsou v tomto smyslu velmi obtížné.

Dáte nám příklad?

Kdybyste si chtěli udělat výlet po České republice a měli jste vybraných dvacet měst, která chcete navštívit, a chtěli ušetřit za benzín i zbytečné cesty, potřebujete najít nejefektivnější cestu. To je takzvaný „problém obchodního cestujícího“. Jedná se o těžký problém v tom smyslu, že pokaždé, když vám dám mapu Česka, budete si muset sednout nad mapu a vymyslet nějaké chytré řešení. Když vám pak dám mapu Německa s dvaceti různými městy, budete muset celý proces začít znovu. Neexistuje žádný recept na to, jak řešit různé problémy téhož druhu.

Nikdo nevěděl, jestli to můžeme počítači říct tak, aby to udělal dobře. Lidé si mysleli, že ne, ale nemohli jsme to dokázat. Existují určité hranice toho, co znamená dokázat, že něco není možné, a existuje velmi specifický způsob řešení problémů, něco, čemu se říká lineární programování, které představuje to největší zobecnění. V naší práci jsme dokázali, že tyto problémy nelze řešit pomocí lineárního programování – potřebujete něco chytřejšího.

IT je velmi progresivní obor. Jak je běžné, že vaše práce je i po deseti letech stále aktuální a dostává ceny?

Existuje jeden obecný jev – mají-li publikace dobrý počáteční ohlas, mají tendenci si vést dobře i později. Takže bych neřekl, že jde o unikátní výsledek v tom smyslu, že je pro výzkumníky užitečný i po tolika letech. Ale řekněme, že jeho rozsah je trochu větší. Každoročně získává mnohem více citací než jiné práce, které jsem napsal. Takže to není příliš neobvyklé, ale není to ani super běžné.

Dotyčný článek má negativní výsledek, který říká, že něco nemůžete udělat. Praktické využití takových článků spočívá v tom, že pokud se snažíte vyřešit nějaký těžký problém, nesnažte se ho řešit tímto způsobem a my jsme poskytli teoretické vysvětlení. V minulosti lidé velmi dobře věděli, že tyto problémy pravděpodobně nebudou řešitelné, takže to není tak, že by se tomu snažili vyhnout, ale tyto problémy tak trochu motivují lidi, aby se snažili o jejich zobecnění.

Jak to vypadá, když pracujete? Používáte více papír, nebo počítač?

Moje práce má řekněme dvě fáze. Jsou týdny, kdy mám většinu času „zatměno“ a čtu si nebo sleduji videa, která ani přímo nesouvisejí s mou prací, ale zaujme mě nějaké obecné téma z matematiky, fyziky nebo čehokoli jiného. Ale pak jsou období, kdy přemýšlím o nějakém problému, a pak je to pořád. Je úplně jedno, co zrovna dělám. Když jdu spát, mám tento problém v hlavě, ráno je i mou první myšlenkou po probuzení. A občas, když něco vypadá slibně, vytáhnu list papíru a snažím se něco napsat, vypracovat nějaký důkaz. Obvykle se to nějakým triviálním způsobem nepodaří. Takže většinu času používám jen svou mysl. Druhou úrovní je pak používání tužky a papíru. Někdy používám i počítač; pokud mám nějaký nápad a nemám důkaz, tak si napíšu simulaci. Ale to je poměrně vzácné, takže většinou je to tužka a papír. Nebo nic.

„Po několika letech se nám oběma s manželkou v téhle zemi a konkrétně v Praze velmi líbí. Je to přátelské místo pro rodinu,“ říká matematik.

Máte nějaký svůj vědecký sen nebo třeba matematický problém, který byste rád vyřešil?

Momentálně jsem se možná už dva nebo tři roky zasekl na jednom problému, který bych rád vyřešil. Opět souvisí s již zmíněným problémem. Existuje jev, jemuž se říká řez polytopem, což je zase taková mapa České republiky a jsou tam dálnice a tak dále a vy chcete zničit spojení mezi dvěma částmi České republiky, ale nechcete na to vynaložit příliš mnoho energie. Chcete přerušit spojení co nejlevnějším způsobem. Pracuji na problému, kterému se říká kvalita řezu, kolik způsobů můžete přerušit.

Posledních deset let pracujete v Praze. Chtěl byste v Česku zůstat i do budoucna?

Nikdy v životě jsem nebyl vázán na konkrétní místo, takže prakticky kdybyste mě přesadili z města A do města B a podařilo se mi udržet si přátele a rodinu, tak to nemá velký význam. V tomto smyslu, když jsem se přestěhoval do Česka, jsem o tom moc nepřemýšlel.

Ale po několika letech se nám oběma s manželkou v téhle zemi a konkrétně v Praze velmi líbí. Je to přátelské místo pro rodinu. Všude jsou parky, přístup k péči o děti je příjemný. Kolegové v práci jsou velmi vstřícní a přátelští. A celkově se mi žije docela dobře, takže bych neřekl, že se z České republiky odstěhuji, nevidím důvod, proč bych to dělal. Jediná možnost by mohla být, že moje žena je ze Španělska a hodně se jí stýská po domově, takže sem tam říká: „Kéž bychom žili ve Španělsku.“ Ale to víte, s postupem času to jsou čím dál tím nesmyslnější sny... Myslím, že tady zůstaneme, ale budoucnost samozřejmě předvídat nelze.

Vím, že vaše žena je také vědkyně. Jaké je její téma?

Ona je také matematička. Učí na Českém vysokém učení technickém (ČVUT) na katedře informatiky a zabývá se oblastí, které se říká výpočetní geometrie –  řešení geometrických úloh pomocí počítače.

Rozumíte si navzájem své práci?

Ano, rozumíme si docela dobře. Mohu říci, že její práci chápu trochu snáze, protože jsem na těchto typech problémů dříve pracoval. Zcela konkrétní problém, na němž momentálně pracuje, bych neznal, ale rozumím obecné oblasti. Jeden z mých prvních příspěvků, který jsem napsal, byl na konferenci nazvané Symposium on Computational geometry. O naší vědě diskutujeme často, zejména pokud máme nějaký problém, se kterým jsme se zasekli nebo si chceme tříbit myšlenky.