نظرية التعقيد احدى اجزاء نظرية الحوسبة و تتعامل مع الموارد المطلوبة في عملية الحوسبة . أكثر هذه الموارد شيوعا هي الزمن (بمعنى كم من الخطوات أو ما يقابلها من الوقت يلزم لحل المسألة ) و المكان (بمعنى ما حجم الذاكرة اللازمة لحل المسألة) ، يمكن ان يدخل بالاعتبار موارد أخرى ، مثل : كم عدد المعالجات المتوازية اللازمة لإنجاز الحساب باستخدام برمجة متوازية .
تختلف نظرية التعقيد عن نظرية الحسوبية في أن نظرية الحسوبية تدرس فيما إذا كانت المسألة قابلة للحساب ام لا بشكل مطلق ، اما نظرية التعقيد فتدرس كيفية إنجاز الحسابات بكفاءة و سرعة .

تعاريف
من المعلوم أن معظم المشاكل يتم محاولة حلها باستعمال الحاسوب, و مع التطور التكنولوجي تتطور سرعة الأداء و يصبح الحاسوب قادرا على إجراء عمليات أكثر تعقيدا, لهذا وجب تحديد تعريف مستقل عن التكنولوجيا, مرتبط فقط بالخوارزميات, فمثلا إذا أخدنا عددين كل منهما مكون من 100 رقم, فإجراء عملية الجمع و الضرب بالحاسوب ستكون تقريبا آنية, فالمستعمل لن يشعر بأي فارق زمني.
إذن نعرف الزمن هنا على أنه عدد العمليات الأولية التي يحتاجها برنامج (خوارزمية) لإجراء العمليات.

الوقت و الزمن

تصنيف
هناك مشاكل سهلة الحل, حيث يتم إيجاد حل لها في وقت وجيز. فمثلا ترتيب مجموعة أعداد من الأصغر إلى الأكبر يتم في وقت قصير, و العلاقة الموجودة بين عدد عناصر المجموعة و الوقت الذي يستغرقه الحاسوب باستعمال خوارزميات الترتيب يعبر عنها بدالة حدودية.
عادة ما يرمز للمشاكل الحدودية المحددة ب: P
أمثلة:

جداء عددين.
القاسم المشترك لعددين.
معرفة هل عدد أولي أم لا. المشاكل الحدودية المحددة
هناك مشاكل صعبة الحل, حيث يتم إيجاد حل لها في وقت جد جد طويل. فمثلا تفكيك عدد إلى جداء أعداد أولية يحتاج إلى وقت طويل كلما كبر العدد, و العلاقة الموجودة بين عدد عناصر المجموعة و الوقت الذي يستغرقه الحاسوب باستعمال خوارزميات الترتيب يعبر عنها بدالة أسية في أغلب الأحيان.
كما أنه إذا كان من الصعب إيجاد الحل, فإنه من السهل التأكد من صحة أو خطأ الجواب, فعملية التأكد و التحقق من الجواب تجرى في وقت حدودي.
عادة ما يرمز للمشاكل الحدودية غير المحددة ب: NP
أمثلة:

مشكلة تلوين المخطط.
مشكلة التفكيك إلى جداء عوامل أولية.
مشكلة المخطط الكامل ضمن مخطط. المشاكل الحدودية غير المحددة
من السهل ملاحظة أن المشاكل المحددة هي ضمن المشاكل غير المحددة, لكن المشكلة العظمى والتي لم يتمكن من الجواب عنها علماء المعلوميات مند سنة 1971 إلى الآن هو هل هناك تساو أو اختلاف بين الصنفين؟ و أول من يتمكن من الإجابة على هذا السؤال يأخد جائزة مالية قدرها 100000$.

المشاكل الحدودية المحددة مقابل المشاكل الحدودية غير المحددة

الاختصار
نقول أن المشكل P, مشكل حدودي غير محدد كامل NP-complet إذا كان أصعب من جميع المشاكل المنتمية إلى صنف المشاكل الحدودية غير المحددة NP. أو كان هناك اختصار حدودي من أي مشكل من صنف NP إلى المشكل P.

تعريف
الاكتفاء (معروف ب SAT) مشكل كامل .

مبرهنة كوك و ليفين

مشكلة تلوين المخطط.
مشكلة التفكيك إلى جداء عوامل أولية.
مشكلة المخطط الكامل ضمن مخطط.
مشكلة الرحالة التاجر. خاصية مهمة للمشاكل الكاملة
ترميز لاندو خاص بالمشاكل ويرمز له ب O (الحرف اللاتيني), يقدم فكرة عن سرعة دالة تتزايد أو تتناقص.
مثلا, عند تحليل خوارزمية ما, يمكن حساب عدد العمليات أو عدد المراحل اللازمة للحل, و قد نجد مثلا: T(n) = 4 n).