کلاس پیچیدگی

کلاس پیچیدگی در نظریه پیچیدگی محاسباتی به مجموعه مسائلی گفته می شود که دارای پیچیدگی شبیه به هم هستند و تعریفی به شکل زیر دارند:
برای مثال کلاس NP مجموعه ای از مسئله های تصمیم گیری هستند که توسط ماشین تورینگ غیرقطعی در زمان چندجمله ای حل می شوند در حالی که PSPACE مجموعه ای از مسئله های تصمیم گیری هستند که توسط ماشین تورینگ قطعی در فضای چندجمله ای حل می شوند. بعضی از کلاس های پیچیدگی مجموعه هایی از مسئله های تابع هستند مانند FP.
جدول زیر بعضی از کلاس های پیچیدگی که از مسئله تصمیم مشتق می شوند را نشان می دهد. اگر X با خط پررنگ به Y در زیر خود وصل باشد، Y زیرمجموعه اکید X است و با خط تیره وصل باشد، Y زیرمجموعه یا مساوی X است.
تا کنون نزدیک به 500 کلاس پیچیدگی معرفی شده اند که در اینجا مهم ترین آنها را می آوریم:
• P: قابل حل در زمان چندجمله ای
• NP: جواب های «بله» قابل بررسی در زمان چندجمله ای
• Co - NP: جواب های «نه» قابل بررسی در زمان چندجمله ای توسط ماشین غیرقطعی
• NP - complete: سخت ترین مسائل در NP
• PH: اجتماع کلاس ها در سلسله مراتب چندجمله ای
• PSPACE: قابل حل با حافظه چندجمله ای
• EXP: قابل حل در زمان نمایی
• NC: قابل حل به صورت کارامد در زمان چندجمله ای لگاریتمی روی کامپیوترهای موازی ( پردازنده های موازی )
• L: قابل حل در فضای لگاریتمی
• P/poly: قابل حل در زمان چندجمله ای با یک «رشته راهنما» که فقط به اندازه ورودی بستگی دارد.
• BPP: قابل حل در زمان چندجمله ای توسط الگوریتم های تصادفی ( جواب احتمالاٌ درست است. )
• MA: قابل حل در زمان چندجمله ای توسط پروتکل مرلین - آرتور
• AM:قابل حل در زمان چندجمله ای توسط پروتکل آرتور - مرلین
• BQP:قابل حل در زمان چندجمله ای روی کامپیوتر کوانتوم ( جواب احتمالاٌ درست است. )
• P#: شمارش راه حل های یک مسئله NP
• PP: چندجمله ای به صورت احتمالاتی ( جواب با احتمال اندکی بزرگتر از ½ درست است. )