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

۱٬۴۴۵ بایت اضافه‌شده ،  ۱۳ سال پیش
(صفحهٔ جدید: '''کلاس پیچیدگی''' در نظریه پیچیدگی محاسباتی به مجموعه مسائلی اطلاق می‌شود که دارای پیچیدگی شبیه...)
 
==مهم‌ترین کلاس‌ها==
تا کنون نزدیک به 500 کلاس پیچیدگی معرفی شده‌اند که در اینجا مهم‌ترین ‌آنها را می‌آوریم:
 
*P:
*P: قابل حل در زمان چندجمله‌ای
*NP:
*NP: جواب‌های «بله» قابل بررسی در زمان چندجمله‌ای
*Co-NP:
*Co-NP: جواب‌های «نه» قابل بررسی در زمان چندجمله‌ای توسط ماشین غیرقطعی
*NP-complete:
*NP-complete: سخت‌ترین مسائل در NP
*PH:
*PH: اجتماع کلاس‌ها در سلسله‌مراتب چندجمله‌ای
*PSPACE:
*PSPACE: قابل حل با حافظه چندجمله‌ای
*EXP:
*EXP: قابل حل در زمان نمایی
*NC:
*NC: قابل حل به صورت کارامد در زمان چندجمله‌ای لگاریتمی روی کامپیوترهای موازی
*L:
*L: قابل حل در فضای لگاریتمی
*P/poly:
*P/poly: قابل حل در زمان چندجمله‌ای با یک «رشته راهنما» که فقط به اندازه ورودی بستگی دارد.
*BPP:
*BPP: قابل حل در زمان چندجمله‌ای توسط [[الگوریتم‌های تصادفی]] (جواب احتمالاٌ درست است.)
*MA:
*MA: قابل حل در زمان چندجمله‌ای توسط [[پروتکل مرلین-آرتور]]
*AM:
*AM:قابل حل در زمان چندجمله‌ای توسط [[پروتکل آرتور-مرلین]]
*BQP:
*BQP:قابل حل در زمان چندجمله‌ای روی [[کامپیوتر کوانتوم]] (جواب احتمالاٌ درست است.)
* P#:
* P#: شمارش راه‌حل‌های یک مسئله NP
*PP:
*PP: چندجمله‌ای به صورت احتمالاتی (جواب با احتمال اندکی بزرگتر از ½ درست است.)
 
==منابع==
*{{یادکرد-ویکی
۲۹۸

ویرایش