Wat wordt niet gebruikt voor een precieze definitie van wat het betekent om een probleem op te lossen met een bepaalde hoeveelheid tijd en ruimte?
Voor een nauwkeurige definitie van wat het betekent om een probleem op te lossen met een bepaalde hoeveelheid tijd en ruimte, wordt een rekenmodel zoals de deterministische Turing-machine gebruikt. De tijd die een deterministische Turingmachine M nodig heeft op invoer x is het totale aantal toestandsovergangen of stappen die de machine maakt voordat deze stopt en het antwoord uitvoert ("ja" of "nee"). Een Turingmachine M werkt binnen de tijd f(n), als de tijd die M nodig heeft voor elke invoer van lengte n maximaal f(n) is. Een beslissingsprobleem A kan in tijd f(n) worden opgelost als er een Turing-machine in tijd f(n) werkt die het probleem oplost. Aangezien de complexiteitstheorie geïnteresseerd is in het classificeren van problemen op basis van hun moeilijkheidsgraad, definieert men reeksen problemen op basis van enkele criteria. De reeks problemen die binnen tijd f(n) op een deterministische Turingmachine kunnen worden opgelost, wordt dan bijvoorbeeld aangeduid met DTIME(f(n)).