1, 2, 3, 4, 5, 6, 7, ...

Slýcháme, že přirozená čísla jsou od Boha - či aspoň od přírody, jak svědčí jejich název -, vše ostatní si lidé nebo matematici vymysleli. Je-li tomu tak, naskýtá se otázka, jakým způsobem čísla v přírodě vůbec existují a jak se my o nich dovídáme.

Nějaké číslo vstupuje do bytí především jako počet něčeho. Na první pohled banální tvrzení, skrývá však háček: co si máme myslet o těch číslech, která shodou okolností nejsou ničeho počtem? Jsou to například hodně velká čísla - těch je dokonce většina! A vůbec, kdo rozhodne, které to entity světa mají povahu počítatelnosti? Když takto začneme uvažovat, brzy se dostaneme k otázce, kolik nám to čísel Bůh vlastně nadělil.

Několik málo nejmenších čísel lze přímo "vidět": stačí se přece podívat, abychom poznali, zda hřib, čáp, kůň, střevlík či pavouk má vždy správný počet nohou. Není nutno počítat. Horizont takovéto viditelnosti je někde mezi osmi a počtem nohou stonožky (který není sto ale 34, u některých druhů až 346, mám-li věřit knihám).

Za tímto horizontem už nezbývá než zdlouhavě počítat, či odpočítávat, jako ovčák ovce, jednu po druhé. Narazíme však brzy na další problém. Běžně máme za to, že počet nějakých reálných věcí, ať je jich sebevíc - počet ovcí v houfu, molekul v roztoku, hvězd v galaxii - je exaktní, objektivní, nezávislý na počítajícím. Představa, že k takto chápanému počtu se lze dobrat počítáním, by však vyžadovala něco závažnějšího než trpělivost: museli bychom počítajícího vysvobodit z našeho reálného času a prostoru. V něm totiž počítání předpokládá určitou prostorovou činnost, přenášení informace z místa na místo, nebo přeskupování počítané množiny - a nic nám přitom nezaručí, že se přitom počítaná množina nějak nepozorovaně nezmění.

Asi je to tak, že od Boha (či od přírody) máme jen malá čísla. Ta velká (rozuměj: větší, než lze v přírodě potkat) si matematici museli domyslet. Dobře udělali, protože se ukázalo, že teoretizovat lze daleko snáze o množině všech čísel vůbec než o některé její části. Hlavním trikem jsou aritmetické operace: sčítání a násobení. Aritmetika umožňuje mluvit o všech číslech najednou v jazyku malých čísel (stačí dokonce jednička) a definovat celou nekonečnou množinu čísel na malém kousku papíru. Stačí vyjít z několika základních zákonů (axiomů a odvozovacích pravidel), vše ostatní lze odvodit. Pozor! Opravdu vše?

Nekonečno, jehož přijetí umožňuje přemítat o množině všech přirozených čísel vcelku a tak o nich mluvit nezávisle na tom, zda jsou velká či malá, se nám vzepřelo dát do rukou vše. Od roku 1931 víme, že ať definujeme přirozená čísla sebelépe, vždy nám některé jejich vlastnosti zůstanou utajeny. Slavná Gödelova věta totiž praví, že žádný (konečný) systém zákonů nemůže být tak silný, aby byl schopen dokázat všechny pravdy o číslech, aniž by přitom nedokázal též nějaké nepravdy.

Existuje intimní souvislost mezi množinami čísel, výroky o číslech a algoritmy, které s čísly operují. Tak například výrok "číslo x je prvočíslo" říká, že číslo x je prvkem množiny prvočísel. K množině prvočísel pak existuje algoritmus (počítačový program), který rozpoznává prvočísla. Vložíme-li na vstup tohoto algoritmu číslo x, odpoví "ano" v případě, že náš výrok byl pravdivý.

Nelze se proto divit, že existuje stejně intimní souvislost mezi teorií čísel a teorií algoritmů. Zatímco teorie čísel je tu s námi již dlouho, je teorie algoritmů záležitostí tohoto století. Její rozvoj v posledních desetiletích je - jak by se dalo čekat - důsledkem existence počítačů. Jak už to bývá, praktické potřeby silně ovlivňují směr teoretického bádání (to je prostě fakt, nikoliv apel) a protože rychlost výpočtu (pro různá vstupní data) je z praktického hlediska snad nejdůležitější vlastností algoritmů, je teorie výpočtové složitosti jednou z nejživějších disciplín informatiky.

V tomto čísle je teorii složitosti věnován článek Pavla Pudláka (Vesmír 74, 305, 1995/6). Teorie výpočtové složitosti nahrazuje otázku principiální existence algoritmu (či důkazu nějakého tvrzení) otázkou existence zvládnutelného algoritmu pro danou úlohu - rozumí se takového, jehož nároky na výpočetní čas nerostou příliš strmě v závislosti na velikosti vstupních dat. Existuje zajímavá třída úloh (mnohé z nich jsou dokonce "ze života"), zvaná "NP", pro něž všechny známé algoritmy hledají řešení jen obtížně (zdlouhavě), přičemž však pokud nějaké řešení spadne z nebe, snadno se pozná, zda je správné. Nezbývá tedy než trpělivě probírat všechny případy, jeden po druhém.

Kdekdo se snaží zjistit, zda s tím lze něco dělat. Kdyby se totiž našel zvládnutelný algoritmus aspoň pro jednu úlohu z jisté dobře popsané podtřídy úloh typu NP, pak by už všechny úlohy typu NP měly zvládnutelný algoritmus.

Situace mi trošičku připomíná rozdíl mezi malými, "viditelnými" čísly a čísly, k nimž se lze jen dopočítávat, jak o tom byla řeč na začátku. Je možné, že ony zvládnutelné algoritmy, založené zpravidla na nějakém vhledu do podstaty úlohy, se vyskytují jen velmi vzácně mezi primitivními a zdlouhavými algoritmy, které neumějí než se probírat všemi možnostmi.