Tuttavia, il fatto di limitare il tempo di calcolo per alcune funzioni concrete f (n) produce spesso classi di complessità che dipendono dal modello di macchina scelto. Ad esempio, la lingua {xx | x è qualsiasi stringa binaria} può essere risolta in tempo lineare su una macchina Turing multifascia, ma richiede necessariamente un tempo quadratico nel modello di macchina Turing monotappo. Se permettiamo variazioni polinomiali nel tempo di esecuzione, la tesi di Cobham-Edmonds afferma che "le complessità temporali in qualsiasi modello di calcolo ragionevole e generale sono polinomialmente correlate" (Goldreich 2008, Capitolo 1.2). Questo costituisce la base per la classe di complessità P, che è l' insieme dei problemi decisionali risolvibili da una macchina deterministica Turing entro il tempo polinomio. La serie di problemi di funzionamento corrispondenti è FP.
Il delimitazione concreta del tempo di calcolo produce spesso classi di complessità in funzione di ciò?
modello di macchina scelto