تفاوت میان نسخه‌های «کلاس پیچیدگی»

برای مثال کلاس '''[[NP]]''' مجموعه‌ای از [[مسئله تصمیم‌گیری|مسئله‌های تصمیم‌گیری]] هستند که توسط [[ماشین تورینگ غیرقطعی]] در [[زمان چندجمله‌ای]] حل می‌شوند در حالی که '''[[PSPACE]]''' مجموعه‌ای از مسئله‌های تصمیم‌گیری هستند که توسط [[ماشین تورینگ قطعی]] در [[فضای چندجمله‌ای]] حل می‌شوند.بعضی از کلاس‌های پیچیدگی مجموعه‌هایی از [[مسئله تابع|مسئله‌های تابع]] هستند مانند '''[[FP]]'''.
==روابط بین کلاس‌های پیچیدگی==
جدول زیر بعضی از کلاس‌های پیچیدگی که از [[مسئله تصمیم]] مشتق می‌شوند را نشان می‌دهد. اگر X با خط پررنگ به Y در زیر خود وصل باشد، Y زیرمجموعه اکید X است و با خط تیره وصل باشد، Y زیرمجموعه و یا مساوی X است.
 
 
</table>
{{پایان چپ چین}}
 
 
==مهم‌ترین کلاس‌ها==
۶٬۹۲۰

ویرایش