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 7066
Třída NPTIME 7661
Třída NP-úplných problémů 8548
Kam dál?