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

از ویکی‌پدیا، دانشنامهٔ آزاد
نمایش تاریخچه به صورت تعاملی
→ تفاوت قدیمی‌ترتفاوت جدیدتر ←
محتوای حذف‌شده محتوای افزوده‌شده
دیداریویکی‌متن
Ebrambot (بحث | مشارکت‌ها)
ربات‌ها
۱۶۴٬۵۲۷ ویرایش‌ها
جز پاک‌سازی فاصله‌های مجازی زائد
Amirobot (بحث | مشارکت‌ها)
ربات‌ها
۵۹۲٬۸۸۴ ویرایش‌ها
جز ربات کاربر: به‌روزرسانی ترکیب جدول
خط ۹: خط ۹:


{{چپ چین}}
{{چپ چین}}

<table cellpadding="0" cellspacing="0" border="0" align="center">
<tr align="center">
{| cellpadding="0" cellspacing="0" border="0" align="center"
|- align="center"
<td colspan=2></td>
| colspan="2" | || colspan="4" |
<td colspan=4><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">مسئله تصمیم‌گیری </td></tr></table></td>
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"
</tr>
|-
<tr align="center">
| align="center" | مسئله تصمیم‌گیری
<td colspan=2></td>
|}
<td>[[پرونده:solidLine.png]]</td>
|- align="center"
<td colspan=2></td>
<td>[[پرونده:solidLine.png]]</td>
| colspan="2" | || [[پرونده:solidLine.png]]
| colspan="2" | || [[پرونده:solidLine.png]]
</tr>
<tr align="center">
|- align="center"
| colspan="3" |
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">نوع صفر - شمارش‌پذیر به صورت بازگشتی</td></tr></table></td>
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"
<td></td>
|-
<td colspan=4><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">غیرقابل تصمیم‌گیری </td></tr></table></td>
| align="center" | نوع صفر - شمارش‌پذیر به صورت بازگشتی
</tr>
|}
<tr align="center">
|
<td colspan=3>[[پرونده:solidLine.png]]</td>
|| colspan="4" |
</tr>
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"
<tr align="center">
|-
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">قابل تصمیم‌گیری</td></tr></table></td>
| align="center" | غیرقابل تصمیم‌گیری
</tr>
|}
<tr align="center">
|- align="center"
<td colspan=3>[[پرونده:solidLine.png]]</td>
| colspan="3" | [[پرونده:solidLine.png]]
</tr>
<tr align="center">
|- align="center"
| colspan="3" |
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">EXPSPACE</td></tr></table></td>
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"
</tr>
|-
<tr align="center">
| align="center" | قابل تصمیم‌گیری
<td colspan=3>[[پرونده:dottedLine.png]]</td>
|}
</tr>
<tr align="center">
|- align="center"
| colspan="3" | [[پرونده:solidLine.png]]
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">EXPTIME</td></tr></table></td>
|- align="center"
</tr>
| colspan="3" |
<tr align="center">
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
<td colspan=3>[[پرونده:dottedLine.png]]</td>
|-
</tr>
<tr align="center">
| align="center" | EXPSPACE
|}
<td colspan=8><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">PSPACE</td></tr></table></td>
|- align="center"
</tr>
| colspan="3" | [[پرونده:dottedLine.png]]
<tr align="center">
|- align="center"
<td>[[پرونده:solidLine.png]]</td>
| colspan="3" |
<td width=40>[[پرونده:dottedLine.png]]</td>
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
<td>[[پرونده:dottedLine.png]]</td>
|-
<td>[[پرونده:dottedLine.png]]</td>
| align="center" | EXPTIME
<td></td>
|}
<td>[[پرونده:dottedLine.png]]</td>
|- align="center"
<td></td>
<td>[[پرونده:dottedLine.png]]</td>
| colspan="3" | [[پرونده:dottedLine.png]]
|- align="center"
</tr>
| colspan="8" |
<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>
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
|-
<td>[[پرونده:dottedLine.png]]</td>
| align="center" | PSPACE
<td>[[پرونده:dottedLine.png]]</td>
|}
<td border="1">[[پرونده:dottedLine.png]]</td>
|- align="center"
<td></td>
<td>[[پرونده:dottedLine.png]]</td>
| [[پرونده:solidLine.png]]
| width="40" | [[پرونده:dottedLine.png]]
<td></td>
| [[پرونده:dottedLine.png]] || [[پرونده:dottedLine.png]]
<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>
|| [[پرونده:dottedLine.png]] || || [[پرونده:dottedLine.png]]
<tr align="center">
|- align="center"
<td>[[پرونده:solidLine.png]]</td>
|
<td>[[پرونده:dottedLine.png]]</td>
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"
<td>[[پرونده:dottedLine.png]]</td>
|-
<td>[[پرونده:dottedLine.png]]</td>
| align="center" | نوع اول - حساس به متن
<td></td>
|}
<td>[[پرونده:dottedLine.png]]</td>
| [[پرونده:dottedLine.png]] || [[پرونده:dottedLine.png]]
</tr>
| border="1" | [[پرونده:dottedLine.png]]
<tr align="center">
|
<td>[[پرونده:solidLine.png]]</td>
<td>[[پرونده:dottedLine.png]]</td>
|| [[پرونده:dottedLine.png]] || || colspan="1" |
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">Co-NP</td></tr></table></td>
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
|-
| align="center" | PSPACE-Complete
|}
<td>[[پرونده:dottedLine.png]]</td>
|- align="center"
<td></td>
<td>[[پرونده:dottedLine.png]]</td>
| [[پرونده:solidLine.png]] || [[پرونده:dottedLine.png]]
| [[پرونده:dottedLine.png]] || [[پرونده:dottedLine.png]] ||
<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>
| [[پرونده:dottedLine.png]]
</tr>
<tr align="center">
|- align="center"
<td>[[پرونده:solidLine.png]]</td>
| [[پرونده:solidLine.png]] || [[پرونده:dottedLine.png]]
|
<td>[[پرونده:dottedLine.png]]</td>
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
<td>[[پرونده:dottedLine.png]]</td>
|-
<td>[[پرونده:dottedLine.png]]</td>
| align="center" | Co-NP
<td></td>
|}
<td>[[پرونده:dottedLine.png]]</td>
| [[پرونده:dottedLine.png]] || || [[پرونده:dottedLine.png]]
<td></td>
| colspan="2" |
<td>[[پرونده:dottedLine.png]]</td>
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
</tr>
|-
<tr align="center">
| align="center" | NP
<td>[[پرونده:solidLine.png]]</td>
|}
<td>[[پرونده:dottedLine.png]]</td>
|- align="center"
<td>[[پرونده:dottedLine.png]]</td>
| [[پرونده:solidLine.png]] || [[پرونده:dottedLine.png]]
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">BPP</td></tr></table></td>
| [[پرونده:dottedLine.png]] || [[پرونده:dottedLine.png]] ||
<td width=10></td>
| [[پرونده:dottedLine.png]] ||
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">BQP</td></tr></table></td>
|| [[پرونده:dottedLine.png]]
<td width=10></td>
|- align="center"
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">NP-Complete</td></tr></table></td>
| [[پرونده:solidLine.png]] || [[پرونده:dottedLine.png]]
</tr>
| [[پرونده:dottedLine.png]] ||
<tr align="center">
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
<td>[[پرونده:solidLine.png]]</td>
|-
<td>[[پرونده:dottedLine.png]]</td>
| align="center" | BPP
<td>[[پرونده:dottedLine.png]]</td>
|}
<td>[[پرونده:dottedLine.png]]</td>
| width="10" | ||
<td></td>
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
<td>[[پرونده:dottedLine.png]]</td>
|-
</tr>
<tr align="center">
| align="center" | BQP
|}
<td>[[پرونده:solidLine.png]]</td>
| width="10" | ||
<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>
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
|-
| align="center" | NP-Complete
|}
</tr>
<tr align="center">
|- align="center"
<td>[[پرونده:solidLine.png]]</td>
| [[پرونده:solidLine.png]] || [[پرونده:dottedLine.png]]
<td>[[پرونده:dottedLine.png]]</td>
| [[پرونده:dottedLine.png]] || [[پرونده:dottedLine.png]] ||
<td>[[پرونده:dottedLine.png]]</td>
| [[پرونده:dottedLine.png]]
|- align="center"
<td colspan=4></td>
<td>[[پرونده:dottedLine.png]]</td>
| [[پرونده:solidLine.png]] || [[پرونده:dottedLine.png]]
| colspan="6" |
</tr>
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
<tr align="center">
|-
<td>[[پرونده:solidLine.png]]</td>
| align="center" | P
<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>
|- align="center"
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">P-Complete</td></tr></table></td>
| [[پرونده:solidLine.png]] || [[پرونده:dottedLine.png]]
</tr>
| [[پرونده:dottedLine.png]]
<tr align="center">
<td>[[پرونده:solidLine.png]]</td>
| colspan="4" | || [[پرونده:dottedLine.png]]
|- align="center"
<td colspan=2>[[پرونده:solidLine.png]]</td>
| [[پرونده:solidLine.png]] || colspan="2" |
</tr>
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
<tr align="center">
|-
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">نوع دوم - متن آزاد</td></tr></table></td>
| align="center" | NC
</tr>
|}
<tr align="center">
| colspan="4" | ||
<td colspan=3>[[پرونده:solidLine.png]]</td>
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
</tr>
|-
<tr align="center">
| align="center" | P-Complete
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">نوع سوم - عادی</td></tr></table></td>
|}
</tr>
|- align="center"
</table>
| [[پرونده:solidLine.png]]
| colspan="2" | [[پرونده:solidLine.png]]
|- align="center"
| colspan="3" |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"
|-
| align="center" | نوع دوم - متن آزاد
|}
|- align="center"
| colspan="3" | [[پرونده:solidLine.png]]
|- align="center"
| colspan="3" |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"
|-
| align="center" | نوع سوم - عادی
|}
|}
{{پایان چپ چین}}
{{پایان چپ چین}}


نسخهٔ ‏۹ اکتبر ۲۰۱۰، ساعت ۱۹:۵۶

کلاس پیچیدگی در نظریه پیچیدگی محاسباتی به مجموعه مسائلی اطلاق می‌شود که دارای پیچیدگی شبیه به هم هستند و تعریفی به شکل زیر دارند:

مجموعه مسائلی که می‌توان آنها را توسط ماشین انتزاعی M با مرتبه یا Order تابعی از n با استفاده از منبع R حل کرد که n اندازه ورودی است.

برای مثال کلاس NP مجموعه‌ای از مسئله‌های تصمیم‌گیری هستند که توسط ماشین تورینگ غیرقطعی در زمان چندجمله‌ای حل می‌شوند در حالی که PSPACE مجموعه‌ای از مسئله‌های تصمیم‌گیری هستند که توسط ماشین تورینگ قطعی در فضای چندجمله‌ای حل می‌شوند.بعضی از کلاس‌های پیچیدگی مجموعه‌هایی از مسئله‌های تابع هستند مانند FP.

روابط بین کلاس‌های پیچیدگی

جدول زیر بعضی از کلاس‌های پیچیدگی که از مسئله تصمیم مشتق می‌شوند را نشان می‌دهد. اگر X با خط پررنگ به Y در زیر خود وصل باشد، Y زیرمجموعه اکید X است و با خط تیره وصل باشد، Y زیرمجموعه و یا مساوی X است.


مسئله تصمیم‌گیری
نوع صفر - شمارش‌پذیر به صورت بازگشتی
colspan="4" |
غیرقابل تصمیم‌گیری
قابل تصمیم‌گیری
EXPSPACE
EXPTIME
PSPACE
نوع اول - حساس به متن
PSPACE-Complete
Co-NP
NP
BPP
BQP
NP-Complete
P
NC
P-Complete
نوع دوم - متن آزاد
نوع سوم - عادی

مهم‌ترین کلاس‌ها

روابط بین مهمترین کلاسهای پیچیدگی.

تا کنون نزدیک به 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». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲ ژوئیه ۲۰۰۸.
  • «لیست بسیار بزرگ از کلاس‌های پیچیدگی».

پیوند به بیرون

نیل ایمرمن. «نمودار مرتبه‌بندی کلاس‌های پیچیدگی».

برگرفته از «https://fa.wikipedia.org/w/index.php?title=کلاس_پیچیدگی&oldid=3921127»