Zeithierarchiesatz (Deterministisch)

Für zeitkonstruierbare Funktionen $f$ und $g$ gilt:

1. Deterministisch: Wenn $f(n)\cdot \log f(n)\in o(g(n))$, dann ist $DTIME(f(n))⊊DTIME(g(n))$.
2. Nichtdeterministisch: Wenn $f(n+1)\in o(g(n))$, dann ist $NTIME(f(n))⊊NTIME(g(n))$.

Intuitiv: Mit asymptotisch mehr Zeit kann man echt mehr Sprachen entscheiden.