מחלקת סיבוכיות

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

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

הכלה בין מחלקות[עריכת קוד מקור | עריכה]

דיאגרמה המתארת את ההכלות של מחלקות הסיבוכיות הנפוצות. עבור חלק מהמחלקות שבאיור לא ידוע האם ההכלה היא הכלה ממש, או שוויון

מחלקת סיבוכיות אחת מוכלת במחלקת סיבוכיות אחרת, אם כל הבעיות במחלקה אחת נמצאות גם במחלקה השנייה. כלומר כמות המשאב שמשמשת במחלקה השנייה מספיקה כדי לפתור את כל הבעיות במחלקה הראשונה.

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

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

יחסים בין מחלקות סיבוכיות[עריכת קוד מקור | עריכה]

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

בעיית הכרעה
SolidLine.png SolidLine.png
בעיות כריעות חיובית (למחצה)
בעיות לא כריעות
SolidLine.png
בעיות כריעות
SolidLine.png
EXPSPACE
DottedLine.png
EXPTIME
DottedLine.png
PSPACE
SolidLine.png DottedLine.png DottedLine.png DottedLine.png DottedLine.png DottedLine.png
שפות תלויות הקשר
DottedLine.png DottedLine.png DottedLine.png DottedLine.png
PSPACE-Complete
SolidLine.png DottedLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png DottedLine.png
Co-NP
DottedLine.png DottedLine.png
NP
SolidLine.png DottedLine.png DottedLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png DottedLine.png DottedLine.png
BPP
BQP
NP-Complete
SolidLine.png DottedLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png DottedLine.png
P
SolidLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png
NC
P-Complete
SolidLine.png SolidLine.png
שפות חסרות הקשר
SolidLine.png
שפות רגולריות

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

  • Complexity Zoo - אינדקס מקיף של מחלקות סיבוכיות