Časová složitost algoritmu je funkce, jejímž argumentem je velikost vstupu (v bitech), a hodnotou funkce je počet kroků algoritmu. Samozřejmě pro různé vstupy téže velikosti může algoritmus pracovat různě dlouho: rozhodující je nejhorší případ, pro který výpočet trvá nejdelší dobu.
Časovou složitost problému pak definujeme jako časovou složitost nejrychlejšího algoritmu (Turingova stroje) schopného tento problém rozhodovat. (Nejrychlejší algoritmus je ten, jehož časová složitost je dána nejpomaleji rostoucí funkcí.) Analogicky je tomu u prostorové složitosti.
Složitostní třída DTIME(f(n)) je množina všech problémů, jejichž časová složitost je nejvýše f(n). (Hm, přísně vzato to není množina, ale v tomto předmětu se nic nestane, když ji budeme za množinu považovat)
Z toho plyne, že jestliže máme dvě třídy DTIME(f(n)) a DTIME(g(n)), a platí, že f(n) ≤ g(n), pak DTIME(f(n)) ⊆
DTIME(g(n)): každý problém, který umíme vyřešit v čase f(n), je možné vyřešit taky v delším čase g(n).
Analogicky pak zavedeme i složitostní třídu pro prostor DSPACE(f(n)). Zde je třeba dát pozor na to, že do spotřeby paměti Turingova stroje se nezapočítává délka vstupu a výstupu na speciální vstupní a výstupní pásce.
Speciální význam má nedeterministický Turingův stroj, který zavádí koncepci nedeterministického výpočtu: stroj může v každém kroku náhodně vybírat z více aplikovatelných pravidel. V důsledku toho mohou některé výpočty s tímtéž vstupem být akceptující a jiné zamítající. Vstup x je strojem akceptován tehdy, jestliže pro něj existuje alespoň jeden akceptující výpočet. Přitom ale spotřebovaný čas není brán jako součet všech možných výpočtů (kterých může být exponenciálně mnoho), ale jako čas nejdelšího z nich. Tím pádem je nedeterministický stroj zvýhodněn oproti deterministickému, který by musel při jeho simulaci projít postupně všechny možné výpočty, a přitom spotřeboval exponenciálně delší čas. Proto platí pro libovolnou funkci f(n):
DTIME(f(n)) ⊆ NTIME(f(n)) ⊆ DTIME(2f(n))
Deterministický stroj je vlastně speciálním případem nedeterministického, když v každém kroku existuje právě jedno aplikovatelné pravidlo. Přestože v praxi většinou používáme deterministické algoritmy, mají nedeterministické Turingovy stroje v teorii složitosti velký význam. Jen ony dovolují přesně charakterizovat skupinu v praxi velmi důležitých tzv. NP-úplných problémů, pro které se neví, jak rychle je lze řešit deterministickými algoritmy.