کلاس پیچیدگی در نظریه پیچیدگی محاسباتی به مجموعه مسائلی گفته میشود که دارای پیچیدگی شبیه به هم هستند و تعریفی به شکل زیر دارند:
مجموعه مسائلی که میتوان آنها را توسط ماشین انتزاعی M با مرتبه یا Order تابعی از n با استفاده از منبع R حل کرد که n اندازه ورودی است.
برای مثال کلاس NP مجموعهای از مسئلههای تصمیمگیری هستند که توسط ماشین تورینگ غیرقطعی در زمان چندجملهای حل میشوند در حالی که PSPACE مجموعهای از مسئلههای تصمیمگیری هستند که توسط ماشین تورینگ قطعی در فضای چندجملهای حل میشوند.بعضی از کلاسهای پیچیدگی مجموعههایی از مسئلههای تابع هستند مانند FP.
روابط بین کلاسهای پیچیدگی
جدول زیر بعضی از کلاسهای پیچیدگی که از مسئله تصمیم مشتق میشوند را نشان میدهد. اگر X با خط پررنگ به Y در زیر خود وصل باشد، Y زیرمجموعه اکید X است و با خط تیره وصل باشد، Y زیرمجموعه یا مساوی X است.
مسئله تصمیمگیری
نوع صفر - شمارشپذیر به صورت بازگشتی
غیرقابل تصمیمگیری
قابل تصمیمگیری
EXPSPACE
EXPTIME
PSPACE
نوع اول - حساس به متن
PSPACE-Complete
Co-NP
NP
BPP
BQP
NP-Complete
P
NC
P-Complete
نوع دوم - متن آزاد
نوع سوم - عادی
مهمترین کلاسها
روابط بین مهمترین کلاسهای پیچیدگی.
تا کنون نزدیک به 500 کلاس پیچیدگی معرفی شدهاند که در اینجا مهمترین آنها را میآوریم:
