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