کلاس پیچیدگی

کلاس پیچیدگی در نظریه پیچیدگی محاسباتی به مجموعه مسائلی گفته می‌شود که دارای پیچیدگی شبیه به هم هستند و تعریفی به شکل زیر دارند:

مجموعه مسائلی که می‌توان آنها را توسط ماشین انتزاعی M با مرتبه یا Order تابعی از n با استفاده از منبع R حل کرد که n اندازه ورودی است.

برای مثال کلاس NP مجموعه‌ای از مسئله‌های تصمیم‌گیری هستند که توسط ماشین تورینگ غیرقطعی در زمان چندجمله‌ای حل می‌شوند در حالی که PSPACE مجموعه‌ای از مسئله‌های تصمیم‌گیری هستند که توسط ماشین تورینگ قطعی در فضای چندجمله‌ای حل می‌شوند.بعضی از کلاس‌های پیچیدگی مجموعه‌هایی از مسئله‌های تابع هستند مانند FP.
 روابط بین کلاس‌های پیچیدگی 
جدول زیر بعضی از کلاس‌های پیچیدگی که از مسئله تصمیم مشتق می‌شوند را نشان می‌دهد. اگر X با خط پررنگ به Y در زیر خود وصل باشد، Y زیرمجموعه اکید X است و با خط تیره وصل باشد، Y زیرمجموعه یا مساوی X است.


 مسئله تصمیم‌گیری  پرونده:solidLine.png  پرونده:solidLine.png نوع صفر - شمارش‌پذیر به صورت بازگشتی  colspan="4" | 
 غیرقابل تصمیم‌گیری پرونده:solidLine.png قابل تصمیم‌گیری پرونده:solidLine.png EXPSPACE پرونده:dottedLine.png EXPTIME پرونده:dottedLine.png PSPACE پرونده:solidLine.png پرونده:dottedLine.png پرونده:dottedLine.png  پرونده:dottedLine.png  پرونده:dottedLine.png   پرونده:dottedLine.png نوع اول - حساس به متن پرونده:dottedLine.png  پرونده:dottedLine.png پرونده:dottedLine.png  پرونده:dottedLine.png   
 PSPACE-Complete پرونده:solidLine.png  پرونده:dottedLine.png پرونده:dottedLine.png  پرونده:dottedLine.png  پرونده:dottedLine.png پرونده:solidLine.png  پرونده:dottedLine.png Co-NP پرونده:dottedLine.png   پرونده:dottedLine.png NP پرونده:solidLine.png  پرونده:dottedLine.png پرونده:dottedLine.png  پرونده:dottedLine.png  پرونده:dottedLine.png   پرونده:dottedLine.png پرونده:solidLine.png  پرونده:dottedLine.png پرونده:dottedLine.png  BPP  
 BQP  
 NP-Complete پرونده:solidLine.png  پرونده:dottedLine.png پرونده:dottedLine.png  پرونده:dottedLine.png  پرونده:dottedLine.png پرونده:solidLine.png  پرونده:dottedLine.png P پرونده:solidLine.png  پرونده:dottedLine.png پرونده:dottedLine.png  پرونده:dottedLine.png پرونده:solidLine.png  NC  
 P-Complete پرونده:solidLine.png پرونده:solidLine.png نوع دوم - متن آزاد پرونده:solidLine.png نوع سوم - عادی

 مهم‌ترین کلاس‌ها 
تا کنون نزدیک به 500 کلاس پیچیدگی معرفی شده‌اند که در اینجا مهم‌ترین آنها را می‌آوریم:

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

 جستارهای وابسته 
 پیچیدگی زمانی
 طراحی الگوریتم
 مهندسی الگوریتم
 P (پیچیدگی)
 NP (پیچیدگی)
 الگوریتم ان‌پی-آسان
 ان‌پی سخت
 ان‌پی کامل
 ان-پی کامل قوی
 مسئله P در مقابل NP
 نظریه پیچیدگی کوانتومی

 منابع 




 پیوند به بیرون 

رده:کلاس پیچیدگی
رده:نظریه پیچیدگی محاسباتی
رده:پیچیدگی محاسباتی