کلاس پیچیدگی: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز ربات افزودن: he:מחלקת סיבוכיות حذف: fr:Classe de complexité اصلاح: zh:复杂性类 |
جز ربات: ویرایش جزئی |
||
خط ۱۵۲:
تا کنون نزدیک به 500 کلاس پیچیدگی معرفی شده‌اند که در اینجا مهم‌ترین آنها را می‌آوریم:
* P: قابل حل در زمان چندجمله‌ای
* NP: جواب‌های «بله» قابل بررسی در زمان چندجمله‌ای
* Co-NP: جواب‌های «نه» قابل بررسی در زمان چندجمله‌ای توسط ماشین غیرقطعی
* NP-complete: سخت‌ترین مسائل در NP
* PH: اجتماع کلاس‌ها در سلسله‌مراتب چندجمله‌ای
* PSPACE: قابل حل با حافظه چندجمله‌ای
* EXP: قابل حل در زمان نمایی
* NC: قابل حل به صورت کارامد در زمان چندجمله‌ای لگاریتمی روی کامپیوترهای موازی
* L: قابل حل در فضای لگاریتمی
* P/poly: قابل حل در زمان چندجمله‌ای با یک «رشته راهنما» که فقط به اندازه ورودی بستگی دارد.
* BPP: قابل حل در زمان چندجمله‌ای توسط [[الگوریتم‌های تصادفی]] (جواب احتمالاٌ درست است.)
* MA: قابل حل در زمان چندجمله‌ای توسط [[پروتکل مرلین-آرتور]]
* AM:قابل حل در زمان چندجمله‌ای توسط [[پروتکل آرتور-مرلین]]
* BQP:قابل حل در زمان چندجمله‌ای روی [[کامپیوتر کوانتوم]] (جواب احتمالاٌ درست است.)
* P#: شمارش راه‌حل‌های یک مسئله NP
* PP: چندجمله‌ای به صورت احتمالاتی (جواب با احتمال اندکی بزرگتر از ½ درست است.)
== منابع ==
* {{یادکرد-ویکی
|پیوند = http://en.wikipedia.org/wiki/Complexity_class
|عنوان = Complexity class
خط ۱۷۶:
|بازیابی = 2 ژوئیه 2008
}}
* {{یادکرد-ویکی
|پیوند = http://en.wikipedia.org/wiki/List_of_complexity_classes
|عنوان = List of complexity classes
خط ۱۸۳:
|بازیابی = 2 ژوئیه 2008
}}
* {{یادکرد وب
| عنوان=لیست بسیار بزرگ از کلاس‌های پیچیدگی
| نشانی= http://qwiki.caltech.edu/wiki/Complexity_Zoo
| |||