کلاس پیچیدگی: تفاوت میان نسخهها
خنثیسازی ویرایش 1380056 ویژه:Contributions/محمد.رضا (بحث کاربر:محمد.رضا) |
جز ربات : جراحی پلاستیک |
||
خط ۱۶: | خط ۱۶: | ||
<tr align="center"> |
<tr align="center"> |
||
<td colspan=2></td> |
<td colspan=2></td> |
||
<td>[[ |
<td>[[تصویر:solidLine.png]]</td> |
||
<td colspan=2></td> |
<td colspan=2></td> |
||
<td>[[ |
<td>[[تصویر:solidLine.png]]</td> |
||
</tr> |
</tr> |
||
<tr align="center"> |
<tr align="center"> |
||
خط ۲۶: | خط ۲۶: | ||
</tr> |
</tr> |
||
<tr align="center"> |
<tr align="center"> |
||
<td colspan=3>[[ |
<td colspan=3>[[تصویر:solidLine.png]]</td> |
||
</tr> |
</tr> |
||
<tr align="center"> |
<tr align="center"> |
||
خط ۳۲: | خط ۳۲: | ||
</tr> |
</tr> |
||
<tr align="center"> |
<tr align="center"> |
||
<td colspan=3>[[ |
<td colspan=3>[[تصویر:solidLine.png]]</td> |
||
</tr> |
</tr> |
||
<tr align="center"> |
<tr align="center"> |
||
خط ۳۸: | خط ۳۸: | ||
</tr> |
</tr> |
||
<tr align="center"> |
<tr align="center"> |
||
<td colspan=3>[[ |
<td colspan=3>[[تصویر:dottedLine.png]]</td> |
||
</tr> |
</tr> |
||
<tr align="center"> |
<tr align="center"> |
||
خط ۴۴: | خط ۴۴: | ||
</tr> |
</tr> |
||
<tr align="center"> |
<tr align="center"> |
||
<td colspan=3>[[ |
<td colspan=3>[[تصویر:dottedLine.png]]</td> |
||
</tr> |
</tr> |
||
<tr align="center"> |
<tr align="center"> |
||
خط ۵۰: | خط ۵۰: | ||
</tr> |
</tr> |
||
<tr align="center"> |
<tr align="center"> |
||
<td>[[ |
<td>[[تصویر:solidLine.png]]</td> |
||
<td width=40>[[ |
<td width=40>[[تصویر:dottedLine.png]]</td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
<td></td> |
<td></td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
<td></td> |
<td></td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
</tr> |
</tr> |
||
<tr align="center"> |
<tr align="center"> |
||
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">نوع اول - حساس به متن</td></tr></table></td> |
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">نوع اول - حساس به متن</td></tr></table></td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
<td border="1">[[ |
<td border="1">[[تصویر:dottedLine.png]]</td> |
||
<td></td> |
<td></td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
<td></td> |
<td></td> |
||
<td colspan=1><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">PSPACE-Complete</td></tr></table></td> |
<td colspan=1><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">PSPACE-Complete</td></tr></table></td> |
||
</tr> |
</tr> |
||
<tr align="center"> |
<tr align="center"> |
||
<td>[[ |
<td>[[تصویر:solidLine.png]]</td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
<td></td> |
<td></td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
</tr> |
</tr> |
||
<tr align="center"> |
<tr align="center"> |
||
<td>[[ |
<td>[[تصویر:solidLine.png]]</td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">Co-NP</td></tr></table></td> |
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">Co-NP</td></tr></table></td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
<td></td> |
<td></td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
<td colspan=2><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">NP</td></tr></table></td> |
<td colspan=2><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">NP</td></tr></table></td> |
||
</tr> |
</tr> |
||
<tr align="center"> |
<tr align="center"> |
||
<td>[[ |
<td>[[تصویر:solidLine.png]]</td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
<td></td> |
<td></td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
<td></td> |
<td></td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
</tr> |
</tr> |
||
<tr align="center"> |
<tr align="center"> |
||
<td>[[ |
<td>[[تصویر:solidLine.png]]</td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">BPP</td></tr></table></td> |
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">BPP</td></tr></table></td> |
||
<td width=10></td> |
<td width=10></td> |
||
خط ۱۰۷: | خط ۱۰۷: | ||
</tr> |
</tr> |
||
<tr align="center"> |
<tr align="center"> |
||
<td>[[ |
<td>[[تصویر:solidLine.png]]</td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
<td></td> |
<td></td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
</tr> |
</tr> |
||
<tr align="center"> |
<tr align="center"> |
||
<td>[[ |
<td>[[تصویر:solidLine.png]]</td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
<td colspan=6><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">P</td></tr></table></td> |
<td colspan=6><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">P</td></tr></table></td> |
||
</tr> |
</tr> |
||
<tr align="center"> |
<tr align="center"> |
||
<td>[[ |
<td>[[تصویر:solidLine.png]]</td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
<td colspan=4></td> |
<td colspan=4></td> |
||
<td>[[ |
<td>[[تصویر:dottedLine.png]]</td> |
||
</tr> |
</tr> |
||
<tr align="center"> |
<tr align="center"> |
||
<td>[[ |
<td>[[تصویر:solidLine.png]]</td> |
||
<td colspan=2><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">NC</td></tr></table></td> |
<td colspan=2><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">NC</td></tr></table></td> |
||
<td colspan=4></td> |
<td colspan=4></td> |
||
خط ۱۳۳: | خط ۱۳۳: | ||
</tr> |
</tr> |
||
<tr align="center"> |
<tr align="center"> |
||
<td>[[ |
<td>[[تصویر:solidLine.png]]</td> |
||
<td colspan=2>[[ |
<td colspan=2>[[تصویر:solidLine.png]]</td> |
||
</tr> |
</tr> |
||
<tr align="center"> |
<tr align="center"> |
||
خط ۱۴۰: | خط ۱۴۰: | ||
</tr> |
</tr> |
||
<tr align="center"> |
<tr align="center"> |
||
<td colspan=3>[[ |
<td colspan=3>[[تصویر:solidLine.png]]</td> |
||
</tr> |
</tr> |
||
<tr align="center"> |
<tr align="center"> |
||
خط ۱۵۰: | خط ۱۵۰: | ||
==مهمترین کلاسها== |
==مهمترین کلاسها== |
||
[[ |
[[تصویر:Complexity-classes-relations.png|thumb|left|300px|روابط بین مهمترین کلاسهای پیچیدگی.]] |
||
تا کنون نزدیک به 500 کلاس پیچیدگی معرفی شدهاند که در اینجا مهمترین آنها را میآوریم: |
تا کنون نزدیک به 500 کلاس پیچیدگی معرفی شدهاند که در اینجا مهمترین آنها را میآوریم: |
||
خط ۲۰۱: | خط ۲۰۱: | ||
[[de:Komplexitätsklasse]] |
[[de:Komplexitätsklasse]] |
||
⚫ | |||
[[en:Complexity class]] |
[[en:Complexity class]] |
||
⚫ | |||
[[fr:Classe de complexité]] |
[[fr:Classe de complexité]] |
||
[[hr:Klasa složenosti]] |
[[hr:Klasa složenosti]] |
||
[[it:Classe di complessità]] |
[[it:Classe di complessità]] |
||
⚫ | |||
[[ja:複雑性クラス]] |
[[ja:複雑性クラス]] |
||
⚫ | |||
[[nl:Complexiteitsgraad]] |
[[nl:Complexiteitsgraad]] |
||
[[pl:Klasa złożoności]] |
[[pl:Klasa złożoności]] |
نسخهٔ ۱۲ نوامبر ۲۰۰۸، ساعت ۱۴:۳۱
کلاس پیچیدگی در نظریه پیچیدگی محاسباتی به مجموعه مسائلی اطلاق میشود که دارای پیچیدگی شبیه به هم هستند و تعریفی به شکل زیر دارند:
- مجموعه مسائلی که میتوان آنها را توسط ماشین انتزاعی M با مرتبه یا Order تابعی از n با استفاده از منبع R حل کرد که n اندازه ورودی است.
برای مثال کلاس NP مجموعهای از مسئلههای تصمیمگیری هستند که توسط ماشین تورینگ غیرقطعی در زمان چندجملهای حل میشوند در حالی که PSPACE مجموعهای از مسئلههای تصمیمگیری هستند که توسط ماشین تورینگ قطعی در فضای چندجملهای حل میشوند.بعضی از کلاسهای پیچیدگی مجموعههایی از مسئلههای تابع هستند مانند FP.
روابط بین کلاسهای پیچیدگی
جدول زیر بعضی از کلاسهای پیچیدگی که از مسئله تصمیم مشتق میشوند را نشان میدهد. اگر X با خط پررنگ به Y در زیر خود وصل باشد، Y زیرمجموعه اکید X است و با خط تیره وصل باشد، Y زیرمجموعه و یا مساوی X است.
مهمترین کلاسها
تا کنون نزدیک به 500 کلاس پیچیدگی معرفی شدهاند که در اینجا مهمترین آنها را میآوریم:
- P: قابل حل در زمان چندجملهای
- NP: جوابهای «بله» قابل بررسی در زمان چندجملهای
- Co-NP: جوابهای «نه» قابل بررسی در زمان چندجملهای توسط ماشین غیرقطعی
- NP-complete: سختترین مسائل در NP
- PH: اجتماع کلاسها در سلسلهمراتب چندجملهای
- PSPACE: قابل حل با حافظه چندجملهای
- EXP: قابل حل در زمان نمایی
- NC: قابل حل به صورت کارامد در زمان چندجملهای لگاریتمی روی کامپیوترهای موازی
- L: قابل حل در فضای لگاریتمی
- P/poly: قابل حل در زمان چندجملهای با یک «رشته راهنما» که فقط به اندازه ورودی بستگی دارد.
- BPP: قابل حل در زمان چندجملهای توسط الگوریتمهای تصادفی (جواب احتمالاٌ درست است.)
- MA: قابل حل در زمان چندجملهای توسط پروتکل مرلین-آرتور
- AM:قابل حل در زمان چندجملهای توسط پروتکل آرتور-مرلین
- BQP:قابل حل در زمان چندجملهای روی کامپیوتر کوانتوم (جواب احتمالاٌ درست است.)
- P#: شمارش راهحلهای یک مسئله NP
- PP: چندجملهای به صورت احتمالاتی (جواب با احتمال اندکی بزرگتر از ½ درست است.)
منابع
- مشارکتکنندگان ویکیپدیا. «Complexity class». در دانشنامهٔ ویکیپدیای انگلیسی، بازبینیشده در ۲ ژوئیه ۲۰۰۸.
- مشارکتکنندگان ویکیپدیا. «List of complexity classes». در دانشنامهٔ ویکیپدیای انگلیسی، بازبینیشده در ۲ ژوئیه ۲۰۰۸.
- «لیست بسیار بزرگ از کلاسهای پیچیدگی».
پیوند به بیرون
نیل ایمرمن. «نمودار مرتبهبندی کلاسهای پیچیدگی».