दिए गए समय और स्थान का उपयोग करके किसी समस्या को हल करने का क्या अर्थ है, इसकी सटीक परिभाषा के लिए, एक कम्प्यूटेशनल मॉडल जैसे की निर्धारणात्मक ट्यूरिंग मशीन का उपयोग किया जाता है। निर्धारणात्मक ट्यूरिंग मशीन M द्वारा इनपुट x के लिए आवश्यक समय स्टेट ट्रांज़िशन या मशीन द्वारा रुकने और ("हाँ" या "नहीं") उत्तर देने से पहले लिए गए कुल चरणों की संख्या होती है। ऐसा कहा जाता है कि यदि लंबाई n के प्रत्येक इनपुट के लिए M द्वारा आवश्यक समय अधिकांशतः f(n) है तो ट्यूरिंग मशीन M समय f(n) के अनुसार संचालित होती है। यदि समय f(n) में संचालित होने वाली निर्धारणात्मक ट्यूरिंग मशीन मौजूद है जो समस्या सुलझा सकती है तो एक निर्णय समस्या A को समय f(n) में सुलझाया जा सकता है। चूंकि जटिलता सिद्धांत समस्याओं को उनकी कठिनाई के आधार पर वर्गीकृत करने से सम्बंधित है, इसलिए कोई कुछ मानदंडों के आधार पर समस्याओं का एक सेट निर्धारित करता है। उदाहरण के लिए, एक निर्धारणात्मक ट्यूरिंग मशीन द्वारा समय f(n) के भीतर सुलझाई गई समस्याओं के सेट को उसके बाद DTIME(f(n)) द्वारा निर्दिष्ट किया जाता है।
स्टेट ट्रांज़िशन
दिए गए समय और स्थान का उपयोग करके किसी समस्या को हल करने का क्या अर्थ है, इसकी सटीक परिभाषा के लिए, एक कम्प्यूटेशनल मॉडल जैसे की निर्धारणात्मक ट्यूरिंग मशीन का उपयोग किया जाता है। निर्धारणात्मक ट्यूरिंग मशीन M द्वारा इनपुट x के लिए आवश्यक समय स्टेट ट्रांज़िशन या मशीन द्वारा रुकने और ("हाँ" या "नहीं") उत्तर देने से पहले लिए गए कुल चरणों की संख्या होती है। ऐसा कहा जाता है कि यदि लंबाई n के प्रत्येक इनपुट के लिए M द्वारा आवश्यक समय अधिकांशतः f(n) है तो ट्यूरिंग मशीन M समय f(n) के अनुसार संचालित होती है। यदि समय f(n) में संचालित होने वाली निर्धारणात्मक ट्यूरिंग मशीन मौजूद है जो समस्या सुलझा सकती है तो एक निर्णय समस्या A को समय f(n) में सुलझाया जा सकता है। चूंकि जटिलता सिद्धांत समस्याओं को उनकी कठिनाई के आधार पर वर्गीकृत करने से सम्बंधित है, इसलिए कोई कुछ मानदंडों के आधार पर समस्याओं का एक सेट निर्धारित करता है। उदाहरण के लिए, एक निर्धारणात्मक ट्यूरिंग मशीन द्वारा समय f(n) के भीतर सुलझाई गई समस्याओं के सेट को उसके बाद DTIME(f(n)) द्वारा निर्दिष्ट किया जाता है।