Pozoruhodný a v teoretické informatice naprosto ojedinělý fakt je, že v této hierarchii tříd je dodnes mnoho základních problémů otevřených. Neumíme dokázat, zda mezi deterministickými a nedeterministickými časovými třídami (např. P a NP) je měřitelný rozdíl. Obdobná situace je v porovnání času a prostoru (např. P a PSPACE). Na vyřešení těchto problémů jsou vypsány finanční prémie v řádu miliónu dolarů. Pokud by se ukázalo, že P=NP, mělo by to v IT obrovský dopad na řešení výpočetně obtížných problémů.
Vyčíslitelnost a složitost výpočtů
Vztahy mezi složitostními třídami
Shrnutí kapitoly
V této kapitole uspořádáme dosud probrané časové a prostorové třídy do jednotné hierarchie. Toto uspořádání nám umožňuje série poznatků ve větě 4.1 ve skriptech I. Černé. Východiskem je, že pro tutéž funkci f(n) je vždy deterministická složitostní třída obsažena v nedeterministické, a časová v prostorové. Prostor (velikost paměti) je tedy mocnější zdroj výpočetní síly než čas.
Studijní materiály
Skripta Černá, kapitola 4.3. Zejména je třeba nastudovat větu 4.17, důkaz jejích částí (a), (b), (d), a část na str. 34 mezi koncem důkazu věty 4.17 a větou 4.19 (tu už ne). Student musí být schopen všechna tvrzení (a) - (e) věty 4.17 schopen vysvětlit a použít při řešení příkladů.
Skripta Wiedermann, kapitoly 4.7 – 4.11. a konec kapitoly 5.1.