کلاس پیچیدگی: تفاوت میان نسخهها
جز ربات: جراحی پلاستیک و زیباسازی |
|||
خط ۴: | خط ۴: | ||
برای مثال کلاس '''[[NP]]''' مجموعهای از [[مسئله تصمیمگیری|مسئلههای تصمیمگیری]] هستند که توسط [[ماشین تورینگ غیرقطعی]] در [[زمان چندجملهای]] حل میشوند در حالی که '''[[PSPACE]]''' مجموعهای از مسئلههای تصمیمگیری هستند که توسط [[ماشین تورینگ قطعی]] در [[فضای چندجملهای]] حل میشوند.بعضی از کلاسهای پیچیدگی مجموعههایی از [[مسئله تابع|مسئلههای تابع]] هستند مانند '''[[FP]]'''. |
برای مثال کلاس '''[[NP]]''' مجموعهای از [[مسئله تصمیمگیری|مسئلههای تصمیمگیری]] هستند که توسط [[ماشین تورینگ غیرقطعی]] در [[زمان چندجملهای]] حل میشوند در حالی که '''[[PSPACE]]''' مجموعهای از مسئلههای تصمیمگیری هستند که توسط [[ماشین تورینگ قطعی]] در [[فضای چندجملهای]] حل میشوند.بعضی از کلاسهای پیچیدگی مجموعههایی از [[مسئله تابع|مسئلههای تابع]] هستند مانند '''[[FP]]'''. |
||
==روابط بین کلاسهای پیچیدگی== |
== روابط بین کلاسهای پیچیدگی == |
||
جدول زیر بعضی از کلاسهای پیچیدگی که از [[مسئله تصمیم]] مشتق میشوند را نشان میدهد. اگر X با خط پررنگ به Y در زیر خود وصل باشد، Y زیرمجموعه اکید X است و با خط تیره وصل باشد، Y زیرمجموعه و یا مساوی X است. |
جدول زیر بعضی از کلاسهای پیچیدگی که از [[مسئله تصمیم]] مشتق میشوند را نشان میدهد. اگر X با خط پررنگ به Y در زیر خود وصل باشد، Y زیرمجموعه اکید X است و با خط تیره وصل باشد، Y زیرمجموعه و یا مساوی X است. |
||
خط ۱۶: | خط ۱۶: | ||
<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 کلاس پیچیدگی معرفی شدهاند که در اینجا مهمترین آنها را میآوریم: |
||
خط ۱۶۹: | خط ۱۶۹: | ||
*PP: چندجملهای به صورت احتمالاتی (جواب با احتمال اندکی بزرگتر از ½ درست است.) |
*PP: چندجملهای به صورت احتمالاتی (جواب با احتمال اندکی بزرگتر از ½ درست است.) |
||
==منابع== |
== منابع == |
||
*{{یادکرد-ویکی |
*{{یادکرد-ویکی |
||
|پیوند = http://en.wikipedia.org/wiki/Complexity_class |
|پیوند = http://en.wikipedia.org/wiki/Complexity_class |
||
خط ۱۸۸: | خط ۱۸۸: | ||
}} |
}} |
||
==پیوند به بیرون== |
== پیوند به بیرون == |
||
{{یادکرد وب |
{{یادکرد وب |
||
| عنوان=نمودار مرتبهبندی کلاسهای پیچیدگی |
| عنوان=نمودار مرتبهبندی کلاسهای پیچیدگی |
||
خط ۱۹۵: | خط ۱۹۵: | ||
}} |
}} |
||
[[رده:ریاضیات گسسته]] |
[[رده:ریاضیات گسسته]] |
||
[[رده: |
[[رده:پیچیدگی محاسباتی]] |
||
[[رده:کلاسهای پیچیدگی]] |
[[رده:کلاسهای پیچیدگی]] |
||
نسخهٔ ۱۳ اوت ۲۰۰۹، ساعت ۱۹:۲۵
کلاس پیچیدگی در نظریه پیچیدگی محاسباتی به مجموعه مسائلی اطلاق میشود که دارای پیچیدگی شبیه به هم هستند و تعریفی به شکل زیر دارند:
- مجموعه مسائلی که میتوان آنها را توسط ماشین انتزاعی 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». در دانشنامهٔ ویکیپدیای انگلیسی، بازبینیشده در ۲ ژوئیه ۲۰۰۸.
- «لیست بسیار بزرگ از کلاسهای پیچیدگی».
پیوند به بیرون
نیل ایمرمن. «نمودار مرتبهبندی کلاسهای پیچیدگی».