در این قسمت به کاری که بتواند توسط کامپیوتر حل شود، مسئله‌ی محاسباتی اطلاق می‌شود (به این معنی که مسئله‌ی مورد نظر بتواند به صورت مجموعه‌ای از دستورالعمل‌های ریاضی بیان شود). یک مسئله‌ی محاسباتی از نمونه‌ مسائل و جواب‌هایی برای آن مسائل تشکیل شده است. به عنوان مثال، آزمون اول بودن[1]، مسئله‌ی تشخیص دادن اول بودن یا نبودن یک عدد معین است. نمونه‌های این مسئله اعداد طبیعی می‌باشند و بر اساس این که یک نمونه اول باشد یا خیر جواب به آن نیز آری یا خیر خواهد بود.

زمانی به یک مسئله ذاتا دشوار اطلاق می‌شود که الگوریتم برای رسیدن به جواب آن نیاز به منابع عمده و قابل توجهی داشته باشد. نظریه‌ي پیچیدگی محاسباتی با وارد کردن مدل‌های محاسباتی به منظور بررسی این مسائل و محاسبه‌ی منابع مورد نیاز برای حل آن‌ها، مثل زمان و حافظه، این مطلب را تحقق می‌بخشد. معیارهای پیچیدگی دیگری مثل میزان ارتباطات (که در پیچیدگی ارتباطی[2] مورد استفاده قرار می‌گیرد)، تعداد گیت‌های منطقی در یک مدار (که در پیچیدگی مداری[3] مورد استفاده قرار می‌گیرد) و تعداد پردازنده‌ها (که در محاسبات موازی مورد[4] استفاده قرار می‌گیرد) نیز مورد استفاده قرار می‌گیرند. یکی از وظایف پیچیدگی محاسباتی این است که محدودیت‌های عملی کامپیوترها را تعیین کند که قادر به انجام چه کارهایی هستند و چه کارهایی را نمی‌توانند انجام دهند.

تحلیل الگوریتم‌ها[5] و نظریه‌ي قابل محاسبه بودن[6] دو زمینه‌ی بسیار مرتبط با هم در علوم نظری کامپیوتر به شمار می‌روند. تفاوت کلیدی بین آن دو در این است که تحلیل الگوریتم‌ها به تعیین میزان منابع مورد نیاز یک الگوریتم خاص برای حل یک مسئله اختصاص دارد در حالی که نظریه‌ي قابل محاسبه بودن پرسشی عمومی‌تر در مورد تمام الگوریتم‌های ممکن که می‌توانند برای حل همان مسئله به کار روند، مطرح می‌کند. به طور دقیق‌تر، این نظریه سعی دارد تا مسائلی را که می‌توانند یا نمی‌توانند با استفاده از تعداد محدود اما مناسبی از منابع حل شوند، طبقه‌بندی کند.


[1]. Primality Testing

[2]. Communication Complexity

[3] . CircuitComplexity

[4] . Parallel Computing

[5]. Analysis of Algorithms

[6] . Computability Theory