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

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

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

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

הכלה בין מחלקות

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

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

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

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

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

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