Může náhoda zefektivnit výpočty s omezenou pamětí?
V oboru teoretické informatiky byl v sérií tří článků J. Šímy a S. Žáka dokázán hluboký výsledek (matematický důkaz zabral zhruba 40 stran), který přispívá k řešení jednoho z ústředních otevřených problémů výpočetní teorie (teorie složitosti). Jeden z těchto článků, vyšel v roce 2011 (LNCS 6651, Berlin: Springer-Verlag, str. 120-133), druhý v roce 2012 (LNCS 7147, Berlin: Springer-Verlag, str. 406-418) a třetí byl zaslán k publikaci. Jde o problém spojený s otázkou, zda náhoda může zefektivnit výpočty s omezenou pamětí. Ilustrujme problém na příkladu z běžného života. Představme si, že se potřebujeme v nám neznámém velkoměstě dopravit autem bez mapy z jednoho místa (start) do jiného (cíl). Takovou úlohu za nás dnes řeší navigace. Situace je komplikována tím, že ve městě jsou jednosměrné ulice, různé nadjezdy, podjezdy, tunely a uzavírky. Jednou z možností je vyjet ze startu a zkoušet systematicky projíždět všechny možné trasy, dokud nedorazíme do cíle. To znamená, že pokud dojedeme do místa, kde jsme již byli, nebo skončíme ve slepé ulici, pak se musíme vrátit zpátky k první křižovatce, ze které vede ulice, kterou jsme ještě neprojeli. Tento postup však vyžaduje, abychom si pamatovali, kde jsme již byli, což může být ve velkém městě se stovkami ulic problém. Jinou možností je náhodný průjezd městem, kdy si na každé křižovatce házíme korunou, zda máme zabočit vlevo či vpravo, resp. vhodnou kostkou, pokud je křižovatka komplikovanější a máme více možností, jak pokračovat v jízdě. Je zajímavé, že se dá matematicky dokázat, že se s velkou pravděpodobností v rozumném čase dostaneme do cíle. Navíc si v tomto případě nemusíme pamatovat již projetou trasu. Naopak hlavní nevýhodou tohoto postupu je, že do cíle nemusíme dorazit vůbec (resp. v daném časovém termínu), i když víme, že možnost selhání náhodného průjezdu je málo pravděpodobná. Otázkou je, zda existuje způsob, jak ze startu s jistotou dojet do cíle, aniž bychom si házeli korunou, pokud jsme schopni si zapamatovat např. jen několik orientačních bodů. Uvedený dopravní problém již postihuje všechny aspekty počítání s omezenou pamětí, takže na něm můžeme studovat obecnou otázku, zda se při těchto výpočtech lze zbavit (málo pravděpodobné) možnosti chyby. Kladná odpověď by přinesla paměťově efektivní a bezchybné řešení pro stovky důležitých praktických problémů. Zásadní význam tohoto problému pro informatiku ilustruje skutečnost, že za vyřešení jeho jednodušší verze (bez jednosměrných ulic) byla mj. v roce 2009 udělena Gödelova cena (obdoba Nobelovy ceny v teoretické informatice). Protože tento problém je velmi těžký pro univerzální modely počítačů (např. Turingovy stroje), zkoumá se na omezených výpočetních modelech. Nám se jej podařilo vyřešit pro tzv. 1-branching programy šířky 3, které se během výpočtu mohou nacházet de facto jen ve 3 stavech (pro řešení původního problému by bylo potřeba dokázat příslušnou matematickou větu pro neomezenou šířku). Ačkoliv je uvedený výpočetní model velmi slabý, námi vyřešený problém byl na nejprestižnějších konferencích v teoretické informatice uváděn jako mez, pro kterou všechny známé techniky selhávají. V chystané monografii (S. Vadhan: Pseudorandomness), která náš výsledek cituje, je tato hranice posunuta na šířku 4, pro kterou je problém doposud otevřený.
