دانلود کتاب Computational Complexity Theory

نظریهٔ پیچیدگی محاسباتی شاخه‌ای از نظریهٔ محاسبات، علوم نظری رایانه و ریاضی است که به بررسی دشواری حل مسائل به وسیلهٔ رایانه(به عبارت دقیق‌تر به صورت الگوریتمی)می‌پردازد. این نظریه بخشی از نظریهٔ محاسباتی است که با منابع مورد نیاز برای حل یک مسئله سروکار دارد.
عمومی‌ترین منابع، زمان (مقدار زمان مورد نیاز برای حل مسئله) و فضا (مقدار حافظه مورد نیاز) می‌باشند. از سایر منابع می‌تواند به تعداد پردازنده‌های موازی (در حالت پردازش موازی) و… اشاره کرد. اما در اینجا عوامل بالا مورد بحث نیستند. باید به این نکته توجه داشت که نظریه پیچیدگی با نظریه قابل حل بودن متفاوت است. این نظریه در مورد قابل حل بودن یک مسئله بدون توجه به منابع مورد نیاز آن، بحث می‌کند. مواردی هست که می‌دانیم یک مسئله جواب دارد ولی راه حل و روش حل آن هنوز ارائه نگردیده و گاهی علاوه بر مشکل مذکور حتی با در دست داشتن راه حل، منابع و ابزار لازم جهت پیاده‌سازی آن مسئله را نداریم.
بعد از این نظریه که بیان می‌کند کدام مسائل قابل حل و کدام مسائل غیرقابل حل هستند، این سؤال به نظر طبیعی می‌رسد که درجه سختی مسئله چقدر است. نظریه پیچیدگی محاسبات در این زمینه‌است.
برای سادگی کار مسئله‌ها به کلاس‌هایی تقسیم می‌شوند، طوری که مسئله‌های یک کلاس از حیث زمان یا فضای مورد نیاز با هم مشابهت دارند. این کلاس‌ها در اصطلاح کلاس‌های پیچیدگی خوانده می‌شوند.