Per una definizione precisa di cosa significhi risolvere un problema utilizzando una determinata quantità di tempo e spazio, si utilizza un modello computazionale come la macchina deterministica Turing. Il tempo richiesto da una macchina deterministica di Turing M all' ingresso x è il numero totale di transizioni di stato, o passi, che la macchina compie prima che si arresti e produca la risposta ("sì" o "no"). Una Turing machine M deve funzionare entro il tempo f (n), se il tempo richiesto da M per ciascun ingresso di lunghezza n è al massimo f (n). Un problema di decisione A può essere risolto nel tempo f (n) se esiste una macchina Turing che funziona nel tempo f (n) che risolve il problema. Poichè la teoria della complessità è interessata a classificare i problemi in base alla loro difficoltà, si definisce una serie di problemi sulla base di alcuni criteri. Ad esempio, l' insieme dei problemi risolvibili entro il tempo f (n) su una macchina deterministica di Turing viene quindi indicato con DTIME (f (n)).
Qual è l' espressione utilizzata per identificare una serie di problemi che possono essere risolti in tempo su una macchina deterministica Turing?
DTIME (f (n)) DTIME (f (n)) DTIME (f (n))