जटिलता सिद्धांत सिर्फ यह नहीं देखता है कि क्या एक समस्या कंप्यूटर पर हल की जा सकती है, बल्कि यह भी देखता है कि यह समस्या कितनी कुशलतापूर्वक हल की जा सकती है। दो प्रमुख पहलुओं पर विचार किया जाता है: समय जटिलता और स्पेस जटिलता, जिसका क्रमशः अर्थ है कि एक अभिकलन को संपादित करने में कितने चरण लगते हैं और उस अभिकलन को संपादित करने में कितनी स्मृति की आवश्यकता होती है।

यह विश्लेषण करने में कि एक दिए गए एल्गोरिथ्म को कितने समय और स्पेस की आवश्यकता है, कंप्यूटर वैज्ञानिक उस समस्या को हल करने के लिए आवश्यक समय और स्पेस को इनपुट समस्या के आकार के फलन के रूप में व्यक्त करते हैं। उदाहरण के लिए, संख्याओं की एक लंबी सूची में एक विशेष संख्या को ढूंढना, संख्या की सूची के लम्बे होने से कठिन होता जाता है। अगर हम कहते हैं कि सूची में formula_1 संख्या है और यदि सूची को किसी भी तरह से हल या अनुक्रमित नहीं किया गया है तो हमें अपनी इच्छित संख्या को खोजने के लिए प्रत्येक संख्या को देखना पड़ सकता है। इस प्रकार हम कह सकते हैं कि इस समस्या को हल करने के लिए, कंप्यूटर को कई चरण संपादित करने की ज़रूरत होगी जो समस्या के आकार में रैखिक रूप से बढ़ता है।

इस समस्या को सरल बनाने के लिए, कंप्यूटर वैज्ञानिकों ने Big O नोटेशन को अपनाया है, जो कार्यों की इस तरह से तुलना करने की अनुमति देता है जो यह सुनिश्चित करता है कि मशीन के निर्माणों के कुछ विशेष पहलुओं पर विचार करने की आवश्यकता नहीं है, बल्कि केवल एसिम्प्टोटिक व्यवहार को देखना होता है जब समस्याएं बड़ी हो जाती हैं। तो हमारे पिछले उदाहरण में, हम कह सकते हैं कि इस समस्या को हल करने के लिए formula_2 चरणों की आवश्यकता है।

शायद सम्पूर्ण कंप्यूटर विज्ञान में सबसे महत्त्वपूर्ण मुक्त समस्या, इस सवाल पर है कि क्या NP चिह्नित समस्याओं का एक निश्चित व्यापक वर्ग कुशलतापूर्वक हल किया जा सकता है कि नहीं। इस पर आगे चलकर जटिलता वर्ग P और NP में चर्चा की गई है।

जटिलता सिद्धांत
कम्प्यूटेबिलिटी सिद्धांत
कंप्यूटिंग का सैद्धांतिक आधार
इन्हें भी देखें