کلاس پیچیدگی: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز ربات افزودن: uk:Обчислювальна складність |
|||
خط ۵:
برای مثال کلاس '''[[NP]]''' مجموعه‌ای از [[مسئله تصمیم‌گیری|مسئله‌های تصمیم‌گیری]] هستند که توسط [[ماشین تورینگ غیرقطعی]] در [[زمان چندجمله‌ای]] حل می‌شوند در حالی که '''[[PSPACE]]''' مجموعه‌ای از مسئله‌های تصمیم‌گیری هستند که توسط [[ماشین تورینگ قطعی]] در [[فضای چندجمله‌ای]] حل می‌شوند.بعضی از کلاس‌های پیچیدگی مجموعه‌هایی از [[مسئله تابع|مسئله‌های تابع]] هستند مانند '''[[FP]]'''.
==روابط بین کلاس‌های پیچیدگی==
جدول زیر بعضی از کلاس‌های پیچیدگی که از [[مسئله تصمیم]] مشتق می‌شوند را نشان می‌دهد. اگر X با خط پررنگ به Y در زیر خود وصل باشد، Y زیرمجموعه اکید X است و با خط تیره وصل باشد، Y زیرمجموعه و یا مساوی X است.
خط ۱۴۷:
</table>
{{پایان چپ چین}}
==مهم‌ترین کلاس‌ها==
| |||