Třídy složitosti

Pro funkci f : rozumíme třídou časové složitosti Τ(f(n)), množinu těch problémů, které jsou řešeny RAMy s časovou složitostí v O(f).
Třídou prostorové složitosti S(f), též S(f(n)), rozumíme třídu těch problémů, které jsou řešeny RAMy s prostorovou složitostí v O(f).

Počet zobrazení 
Titulek Zobrazení
Třída PTIME 5912
Třída NPTIME 6494
Třída NP-úplných problémů 6715
Kam dál?