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

بدون خلاصه ویرایش
(نجات ۲ منبع و علامت‌زدن ۰ به‌عنوان مرده.) #IABot (v2.0)
برچسب‌ها: ویرایش با تلفن همراه ویرایش با مرورگر تلفن همراه ویرایش‌گر دیداری
 
:مجموعه مسائلی که می‌توان آنها را توسط [[ماشین انتزاعی]] M با مرتبه یا Order تابعی از n با استفاده از منبع R حل کرد که n اندازه ورودی است.
 
برای مثال کلاس '''[[NP]]''' مجموعه‌ای از [[مسئله تصمیم‌گیری|مسئله‌های تصمیم‌گیری]] هستند که توسط [[ماشین تورینگ غیرقطعی]] در [[زمان چندجمله‌ای]] حل می‌شوند در حالی که '''[[PSPACE]]''' مجموعه‌ای از [[مسئله‌های تصمیم‌گیری]] هستند که توسط [[ماشین تورینگ قطعی]] در [[فضای چندجمله‌ای]] حل می‌شوند.بعضی از کلاس‌های پیچیدگی مجموعه‌هایی از [[مسئله تابع|مسئله‌های تابع]] هستند مانند '''[[FP]]'''.
== روابط بین کلاس‌های پیچیدگی ==
جدول زیر بعضی از کلاس‌های پیچیدگی که از [[مسئله تصمیم]] مشتق می‌شوند را نشان می‌دهد. اگر X با خط پررنگ به Y در زیر خود وصل باشد، Y زیرمجموعه اکید X است و با خط تیره وصل باشد، Y زیرمجموعه یا مساوی X است.