نظرية التعقيد هي فرع من فروع نظرية الحوسبة والرياضيات، وتتركز في تصنيف المسائل الحاسوبية حسب صعوبتها وربط أقسام التعقيد complexity classes ببعضها البعض. والمسألة الحاسوبية هي المسألة التي يستطيع الحاسوب حلها.
ويمكن اعتبارها مسألة صعبة إذا استخدمت كمية مُعينة من الموارد أياً كانت الخوارزمية. ولعل النماذج الحسابية هي الطريقة الأمثل في هذه النظرية لدراسة هذه المسائل وتحديد كمية الموارد اللازمة لها مثل: الوقت أو حجم المكان الإضافي اللازم، وتوجد معايير تعقيد أخرى مثل: الاتصال (مستخدم في نظرية تعقيد الاتصال) وعدد البوابات في الدارات المنطقية (مستخدم في نظرية تعقيد الدارات المنطقية) وكذلك عدد المعالجات (مستخدم في الحساب المتوازي).
وأحد أهم أساسيات نظرية التعقيد الحسابي هو تحديد ما يمكن للحاسوب فعله، وما لا يمكنه فعله.
المجالات القريبة في علم الحاسوب النظري هي تحليل الخوارزميات والنظرية الحاسوبية، والفرق بين تحليل الخوارزميات ونظرية التعقيد الحسابي هو أن الأول يسأل عن خوارزمية معينة لحل مسألة، بينما الآخر يسأل عن كل الخوارزميات التي يمكنها حل المسألة، وبالتحديد، فإن الأخير يحاول تصنيف المسائل التي يمكن حلها أو عدم حلها بوضع كمية محددة من الموارد. أما وضع الحدود للموارد الموجودة، فهو ما يميز نظرية التعقيد الحسابي عن النظرية الحاسوبية، إذ إن النظرية الحاسوبية تسأل عن أية مسائل يمكن حلها بواسطة خوارزمية. بينما الآخر يسأل عن كل الخوارزميات التي يمكنها حل المسألة، وبالتحديد، فإن الأخير يحاول تصنيف المسائل التي يمكن حلها أو عدم حلها بوضع كمية محددة من الموارد. أما وضع الحدود للموارد الموجودة، فهو ما يميز نظرية التعقيد الحسابي عن النظرية الحاسوبية.