Složité a obtížné

Nebyli bychom lidi, kdybychom se tu a tam neocitli ve složité situaci, kterou jen obtížně zvládáme. Příjemné to není, nejraději bychom všechno měli jednoduché a snadné. Jen co jsem to napsal, už nesouhlasím. Kdyby všechno bylo jednoduché a všechno snadné, kde bychom byli? Nudný by to byl svět, opravdu.

Je zajisté mnoho sfér lidské činnosti, v nichž rozlišování mezi složitým a jednoduchým hraje klíčovou roli. Například ve vědeckém bádání a technickém budování. To, co je složité, je nesrozumitelné, nepopsatelné, nepředvídatelné a neovladatelné, je to spíše poruchové, zranitelné, křehké, drahé a jinak choulostivé. Přesto je složitost, či spíše jistá její podoba – někdy zvaná „komplexita“ – též principem tvořivým: nikoliv kvantita (jak nás zjednodušeně učili), ale komplexita se mění v kvalitu. Aspoň překročí-li jakousi mez, pak to ale stojí za to. Příkladem jsou organizmy, zejména poté, co se kdysi dávno začaly starat samy o sebe a odolávat nástrahám světa.

V posledních desetiletích se pěstují dva pozoruhodné vědní obory, které si za své téma i název vybraly právě složitost. Jedním je věda o složitosti (Science of Complexity), druhým teorie výpočtové složitosti (Complexity Theory).

Věda o složitosti je vzorně transdisciplinární (s těžištěm u teorie systémů a matematické fyziky). Do širší známosti pronikla mimo jiné po založení známého vědeckého ústavu v Santa Fe začátkem 80. let. ¹⁾ Sám pojem složitosti, vztažený zde hlavně k dynamickým systémům, si vysloužil řadu rozmanitých definic; jedna namátkou z českého webu: „systém označíme za složitý, pokud se skládá z řady navzájem interagujících komponent a objevuje se u něj nové chování, které není samozřejmým důsledkem chování jednotlivých komponent.“ Složitost je v tomto smyslu spíše vlastností než veličinou a jako vlastnost je protikladem nejen jednoduchosti, ale i plané neuspořádanosti. ²⁾

Druhý obor, teorie výpočtové (popřípadě algoritmické) složitosti, je součástí matematické informatiky. V tomto čísle (v příspěvku Pavla Pudláka na s. 10) je popsán jeden konkrétní úspěch této teorie: byl nalezen polynomiální (což znamená „snadný“, jak uvidíme) algoritmus, jenž pro jakékoliv číslo, které si vymyslíte, pozná, zda je to prvočíslo.

To, o co tu jde, není složitost věcí, nýbrž problémů a algoritmů a pro odlišení ji budu nazývat obtížnost, nikoliv složitost. Nejprve co rozumíme úlohou, algoritmem, výpočtem. Příklad obecné úlohy:

Pro libovolné přirozené číslo x urči, zda je dělitelné třemi.

Ze školy si pro ni dokonce pamatuji chytrý algoritmus:

Sčítej cifry čísla x, a to opakovaně, dokud nezískáš jednociferné číslo;

je-li toto číslo dělitelné třemi, odpověz ANO, jinak NE.

Tento algoritmus je ovšem také obecný, teprve při zadání vstupu (hodnoty parametru x) jej lze použít k řízení konkrétního výpočtu (což je formálně posloupnost elementárních početních kroků). Pokud výpočet skončí (což se v našem případě vždy stane), dostaneme výsledek (řešení úlohy, zde odpověď ANO, nebo NE). Čtenář nechť si to zkusí třeba pro x = 72321. ³⁾

Nic obtížného – v tomto případě. V jiných případech je to horší. Teorie výpočtové složitosti proto potřebuje obecnou definici obtížnosti (výpočtu, algoritmu, úlohy). Začněme u výpočtu: ten může být zdlouhavý (když je třeba provést velký počet elementárních kroků), nebo paměťově náročný (užívá velký počet míst v pracovní paměťi).

Definovat obtížnost algoritmu je náročnější, musíme počítat s tím, že při různých vstupech jednomu algoritmu odpovídá nekonečně mnoho různých výpočtů o rozličném stupni obtížnosti. Postup je tento: zvolíme nějakou vhodnou míru velikosti vstupu (u čísla například délku čili počet cifer) a sledujeme, jak pro daný algoritmus obtížnost výpočtu závisí na velikosti vstupu. Nepřekvapí nás asi, že čím větší vstup, tím obtížnější výpočet, více nás bude ovšem zajímat, zda lze tento růst obtížnosti omezit shora nějakou rozumnou funkcí. Touto funkcí může být například polynom. Všebecně (a odůvodněně) se předpokládá, že polynomiální nárůst (na rozdíl například od exponenciálního) přirozeně vymezuje kategorii „snadných“ (zvládnutelných) algoritmů. ⁴⁾ To lze zobecnit: úloha je snadná, existuje-li pro ni aspoň jeden polynomiální (tedy „snadný“ algoritmus). ⁵⁾

Teorie složitosti sama o sobě by mohla nabídnout materiál i pro „vědu o vědě“. Lze zde například sledovat jemný rozdíl mezi motivací teoretika a praktika: prvého zajímají obecná tvrzení, konkrétní příklady hledá, jen aby si třeba ověřil, že něco existuje. Důkaz, že úloha je obtížná, má pro něj stejnou hodnotu jako důkaz, že je snadná, a je-li snadná, nevadí mu, když se snadnost uplatní až pro astronomicky velké vstupy. Praktik se naopak zajímá o konkrétní algoritmy na řešení úloh „ze života“ a těší ho, když najde algoritmus snadný i pro malé vstupy.

Objevy teoretika jsou principiální, objevy praktika užitečné. Zpravidla však nelze a ani nemá smysl rozlišovat, zda převládá motivace prvého či druhého. To platí, myslím, i o zmíněném případu rozpoznávání prvočísel.