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

جز
ربات: جراحی پلاستیک و زیباسازی
جز (ربات: جراحی پلاستیک و زیباسازی)
 
برای مثال کلاس '''[[NP]]''' مجموعه‌ای از [[مسئله تصمیم‌گیری|مسئله‌های تصمیم‌گیری]] هستند که توسط [[ماشین تورینگ غیرقطعی]] در [[زمان چندجمله‌ای]] حل می‌شوند در حالی که '''[[PSPACE]]''' مجموعه‌ای از مسئله‌های تصمیم‌گیری هستند که توسط [[ماشین تورینگ قطعی]] در [[فضای چندجمله‌ای]] حل می‌شوند.بعضی از کلاس‌های پیچیدگی مجموعه‌هایی از [[مسئله تابع|مسئله‌های تابع]] هستند مانند '''[[FP]]'''.
== روابط بین کلاس‌های پیچیدگی ==
جدول زیر بعضی از کلاس‌های پیچیدگی که از [[مسئله تصمیم]] مشتق می‌شوند را نشان می‌دهد. اگر X با خط پررنگ به Y در زیر خود وصل باشد، Y زیرمجموعه اکید X است و با خط تیره وصل باشد، Y زیرمجموعه و یا مساوی X است.
 
<tr align="center">
<td colspan=2></td>
<td>[[تصویرپرونده:solidLine.png]]</td>
<td colspan=2></td>
<td>[[تصویرپرونده:solidLine.png]]</td>
</tr>
<tr align="center">
</tr>
<tr align="center">
<td colspan=3>[[تصویرپرونده:solidLine.png]]</td>
</tr>
<tr align="center">
</tr>
<tr align="center">
<td colspan=3>[[تصویرپرونده:solidLine.png]]</td>
</tr>
<tr align="center">
</tr>
<tr align="center">
<td colspan=3>[[تصویرپرونده:dottedLine.png]]</td>
</tr>
<tr align="center">
</tr>
<tr align="center">
<td colspan=3>[[تصویرپرونده:dottedLine.png]]</td>
</tr>
<tr align="center">
</tr>
<tr align="center">
<td>[[تصویرپرونده:solidLine.png]]</td>
<td width=40>[[تصویرپرونده:dottedLine.png]]</td>
<td>[[تصویرپرونده:dottedLine.png]]</td>
<td>[[تصویرپرونده:dottedLine.png]]</td>
<td></td>
<td>[[تصویرپرونده:dottedLine.png]]</td>
<td></td>
<td>[[تصویرپرونده:dottedLine.png]]</td>
</tr>
<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>[[تصویرپرونده:dottedLine.png]]</td>
<td>[[تصویرپرونده:dottedLine.png]]</td>
<td border="1">[[تصویرپرونده:dottedLine.png]]</td>
<td></td>
<td>[[تصویرپرونده:dottedLine.png]]</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>
</tr>
<tr align="center">
<td>[[تصویرپرونده:solidLine.png]]</td>
<td>[[تصویرپرونده:dottedLine.png]]</td>
<td>[[تصویرپرونده:dottedLine.png]]</td>
<td>[[تصویرپرونده:dottedLine.png]]</td>
<td></td>
<td>[[تصویرپرونده:dottedLine.png]]</td>
</tr>
<tr align="center">
<td>[[تصویرپرونده:solidLine.png]]</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>[[تصویرپرونده:dottedLine.png]]</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>
</tr>
<tr align="center">
<td>[[تصویرپرونده:solidLine.png]]</td>
<td>[[تصویرپرونده:dottedLine.png]]</td>
<td>[[تصویرپرونده:dottedLine.png]]</td>
<td>[[تصویرپرونده:dottedLine.png]]</td>
<td></td>
<td>[[تصویرپرونده:dottedLine.png]]</td>
<td></td>
<td>[[تصویرپرونده:dottedLine.png]]</td>
</tr>
<tr align="center">
<td>[[تصویرپرونده:solidLine.png]]</td>
<td>[[تصویرپرونده:dottedLine.png]]</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 width=10></td>
</tr>
<tr align="center">
<td>[[تصویرپرونده:solidLine.png]]</td>
<td>[[تصویرپرونده:dottedLine.png]]</td>
<td>[[تصویرپرونده:dottedLine.png]]</td>
<td>[[تصویرپرونده:dottedLine.png]]</td>
<td></td>
<td>[[تصویرپرونده:dottedLine.png]]</td>
</tr>
<tr align="center">
<td>[[تصویرپرونده:solidLine.png]]</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>
</tr>
<tr align="center">
<td>[[تصویرپرونده:solidLine.png]]</td>
<td>[[تصویرپرونده:dottedLine.png]]</td>
<td>[[تصویرپرونده:dottedLine.png]]</td>
<td colspan=4></td>
<td>[[تصویرپرونده:dottedLine.png]]</td>
</tr>
<tr align="center">
<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=4></td>
</tr>
<tr align="center">
<td>[[تصویرپرونده:solidLine.png]]</td>
<td colspan=2>[[تصویرپرونده:solidLine.png]]</td>
</tr>
<tr align="center">
</tr>
<tr align="center">
<td colspan=3>[[تصویرپرونده:solidLine.png]]</td>
</tr>
<tr align="center">
{{پایان چپ چین}}
 
== مهم‌ترین کلاس‌ها ==
[[تصویرپرونده:Complexity-classes-relations.png|thumb|left|300px|روابط بین مهمترین کلاسهای پیچیدگی.]]
تا کنون نزدیک به 500 کلاس پیچیدگی معرفی شده‌اند که در اینجا مهم‌ترین ‌آنها را می‌آوریم:
 
*PP: چندجمله‌ای به صورت احتمالاتی (جواب با احتمال اندکی بزرگتر از ½ درست است.)
 
== منابع ==
*{{یادکرد-ویکی
|پیوند = http://en.wikipedia.org/wiki/Complexity_class
}}
 
== پیوند به بیرون ==
{{یادکرد وب
| عنوان=نمودار مرتبه‌بندی کلاس‌های پیچیدگی
}}
 
[[رده:ریاضیات گسسته]]
[[رده: پیچیدگی محاسباتی]]
[[رده:کلاس‌های پیچیدگی]]
 
۱۸۶٬۰۵۸

ویرایش