הצגת המקור של הדף "מחלקת סיבוכיות"

ב[[מדעי המחשב]] וב[[תורת הסיבוכיות]], '''מחלקת סיבוכיות''' היא אוסף בעיות בעלות [[סיבוכיות]] משותפת.
בדרך כלל מחלקת סיבוכיות מוגדרת באופן הבא:

אוסף הבעיות שניתן לפתור על ידי מכונה מופשטת <math>\,M</math> תוך שימוש ב- <math>\,O(f(n))</math> ממשאב <math>\,R</math>, כאשר <math>\,n</math> הוא גודל הקלט.

לדוגמה, המחלקה [[NP (סיבוכיות)|NP]] היא מחלקת כל [[בעיית הכרעה|בעיות ההכרעה]] שניתן לפתור על ידי [[מכונת טיורינג לא-דטרמיניסטית]] ב[[סיבוכיות זמן]] [[פולינום|פולינומית]], בעוד שהמחלקה [[PSPACE]] היא מחלקת כל בעיות ההכרעה שניתן לפתור על ידי [[מכונת טיורינג|מכונת טיורינג דטרמיניסטית]] ב[[סיבוכיות מקום]] פולינומית.

== הכלה בין מחלקות ==
[[קובץ:Complexity subsets pspace.svg|שמאל|ממוזער|250px|דיאגרמה המתארת את ההכלות של מחלקות הסיבוכיות הנפוצות. עבור חלק מהמחלקות שבאיור לא ידוע האם ההכלה היא הכלה ממש, או שוויון]]
מחלקת סיבוכיות אחת מוכלת במחלקת סיבוכיות אחרת, אם כל הבעיות במחלקה אחת נמצאות גם במחלקה השנייה. כלומר כמות המשאב שמשמשת במחלקה השנייה מספיקה כדי לפתור את כל הבעיות במחלקה הראשונה.

דוגמה להכלה טריוויאלית היא הכלה של מחלקת כל בעיות ההכרעה שניתן לפתור בזמן פולינומי (המחלקה [[P (סיבוכיות)|P]]) במחלקת בעיות ההכרעה שניתן לפתור בזמן [[פונקציה מעריכית|מעריכי]] (המחלקה [[EXPTIME]]). זאת כיוון שכל בעיה שניתן לפתור בזמן פולינומי, ממילא ניתן לפתור גם בזמן מעריכי.

באותה צורה, מחלקת בעיות ההכרעה שניתן לפתור ב'''זמן''' פולינומי (המחלקה [[P (סיבוכיות)|P]]) מוכלת במחלקת בעיות ההכרעה שניתן לפתור ב'''מקום''' פולינומי (המחלקה [[PSPACE]]). ההסבר לכך הוא שבהינתן בעיה שניתן לפתור בזמן פולינומי - הפתרון לבעיה לא יכול לצרוך יותר ממקום פולינומי, שכן עצם המעבר על כמות תאי זיכרון סופר-פולינומית כבר צורכת זמן סופר-פולינומי. לכן פתרון בזמן פולינומי צורך לכל היותר מקום פולינומי.

== יחסים בין מחלקות סיבוכיות ==
הטבלה הבאה מציגה חלק ממחלקות הסיבוכיות. אם מחלקה '''X''' חלקית ממש למחלקה '''Y''' אזי '''X''' מוצגת מתחת ל '''Y''' עם קו מלא ביניהן. 
אם מחלקה '''X''' חלקית למחלקה '''Y''', אך לא ידוע אם הן שוות, אזי '''X''' מוצגת מתחת ל '''Y''' עם קו מקווקו ביניהן. 

{| cellpadding="0" cellspacing="0" border="0" align="center"
|- align="center"
| colspan=2|
| colspan=4|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"|-
| align="center"|[[בעיית הכרעה]]
|}
|- align="center"
| colspan=2|
|[[קובץ:solidLine.png]]
| colspan=2|
|[[קובץ:solidLine.png]]
|- align="center"
| colspan=3|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"|-
| align="center"|[[קבוצה ניתנת למנייה רקורסיבית|בעיות כריעות חיובית (למחצה)]]
|}
|
| colspan=4|
{| 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"|[[קבוצה רקורסיבית|בעיות כריעות]]
|}
|- align="center"
| colspan=3|[[קובץ:solidLine.png]]
|- align="center"
| colspan=3|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"|-
| align="center"|[[EXPSPACE]]
|}
|- align="center"
| colspan=3|[[קובץ:dottedLine.png]]
|- align="center"
| colspan=3|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"|-
| align="center"|[[EXPTIME]]
|}
|- align="center"
| colspan=3|[[קובץ:dottedLine.png]]
|- align="center"
| colspan=8|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"|-
| align="center"|[[PSPACE]]
|}
|- align="center"
|[[קובץ:solidLine.png]]
| width=40|[[קובץ:dottedLine.png]]
|[[קובץ:dottedLine.png]]
|[[קובץ:dottedLine.png]]
|
|[[קובץ:dottedLine.png]]
|
|[[קובץ:dottedLine.png]]
|- align="center"
|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"|-
| align="center"|[[שפה תלוית הקשר|שפות תלויות הקשר]]
|}
|[[קובץ:dottedLine.png]]
|[[קובץ:dottedLine.png]]
| border="1"|[[קובץ:dottedLine.png]]
|
|[[קובץ:dottedLine.png]]
|
| colspan=1|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"|-
| align="center"|[[PSPACE-Complete]]
|}
|- align="center"
|[[קובץ:solidLine.png]]
|[[קובץ:dottedLine.png]]
|[[קובץ:dottedLine.png]]
|[[קובץ:dottedLine.png]]
|
|[[קובץ:dottedLine.png]]
|- align="center"
|[[קובץ:solidLine.png]]
|[[קובץ:dottedLine.png]]
|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"|-
| align="center"|[[Co-NP]]
|}
|[[קובץ:dottedLine.png]]
|
|[[קובץ:dottedLine.png]]
| colspan=2|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"|-
| align="center"|[[NP (סיבוכיות)|NP]]
|}
|- align="center"
|[[קובץ:solidLine.png]]
|[[קובץ:dottedLine.png]]
|[[קובץ:dottedLine.png]]
|[[קובץ:dottedLine.png]]
|
|[[קובץ:dottedLine.png]]
|
|[[קובץ:dottedLine.png]]
|- align="center"
|[[קובץ:solidLine.png]]
|[[קובץ:dottedLine.png]]
|[[קובץ:dottedLine.png]]
|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"|-
| align="center"|[[BPP]]
|}
| width=10|
|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"|-
| align="center"|[[BQP]]
|}
| width=10|
|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"|-
| align="center"|[[NP-Complete]]
|}
|- align="center"
|[[קובץ:solidLine.png]]
|[[קובץ:dottedLine.png]]
|[[קובץ:dottedLine.png]]
|[[קובץ:dottedLine.png]]
|
|[[קובץ:dottedLine.png]]
|- align="center"
|[[קובץ:solidLine.png]]
|[[קובץ:dottedLine.png]]
| colspan=6|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"|-
| align="center"|[[P (סיבוכיות)|P]]
|}
|- align="center"
|[[קובץ:solidLine.png]]
|[[קובץ:dottedLine.png]]
|[[קובץ:dottedLine.png]]
| colspan=4|
|[[קובץ:dottedLine.png]]
|- align="center"
|[[קובץ:solidLine.png]]
| colspan=2|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"|-
| align="center"|[[NC (סיבוכיות)|NC]]
|}
| colspan=4|
|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"|-
| align="center"|[[P-Complete]]
|}
|- align="center"
|[[קובץ: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"|[[שפה רגולרית| שפות רגולריות]]
|}
|}

== ראו גם ==
* [[סיבוכיות זמן]]
* [[סיבוכיות מקום]]
* [[NP-קשה]]
* [[בעיה NP-שלמה]]
* [[P=NP]]

== קישורים חיצוניים ==
* [https://complexityzoo.uwaterloo.ca/Complexity_Zoo Complexity Zoo] {{Webarchive|url=https://web.archive.org/web/20190827233504/https://complexityzoo.uwaterloo.ca/Complexity_Zoo |date=2019-08-27 }} - אינדקס מקיף של מחלקות סיבוכיות {{אנגלית}}

[[קטגוריה:מחלקות סיבוכיות|*]]