کلاس پیچیدگی

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

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

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

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

• «لیست بسیار بزرگ از کلاس‌های پیچیدگی». بایگانی‌شده از اصلی در ۲۸ نوامبر ۲۰۰۶. دریافت‌شده در ۳ ژوئیه ۲۰۰۸.

نیل ایمرمن. «نمودار مرتبه‌بندی کلاس‌های پیچیدگی». بایگانی‌شده از اصلی در ۱۶ آوریل ۲۰۱۶. دریافت‌شده در ۳ ژوئیه ۲۰۰۸.