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

זוהי רשימה של מחלקות סיבוכיות בתורת הסיבוכיות.

לרבות ממחלקות אלו יש שותף 'co' שמורכב מהשפות המשלימות של כל השפות במחלקה המקורית. למשל, אם שפה L היא ב-NP אז המשלימה של L נמצאת ב-co-NP. (אין הכוונה שהמשלים של NP הוא co-NP—ישנן שפות שידוע כי נמצאות בשתי הקבוצות, ושפות אחרות שידוע שאינן נמצאות בשתיהן.)

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

#Pסופר את מספר הפתרונות של בעיה ב-NP#P-completeהבעיות הקשות ביותר ב-#P2-EXPTIMEפתירות בזמן אקספוננט כפולAC0מחלקה של סיבוכיות מעגלים עם עומק חסום.ACC0מחלקה של סיבוכיות מעגלים עם עומק חסום ושערים מונים.ACמחלקה של סיבוכיות מעגלים.AHההיררכיה האריתמטית.APמחלקת הבעיות שניתנות לפתרון בזמן פולינומי באמצעות מכונת טיורינג מתחלפת (ATM)APXבעיות אופטימיזציה להן קיים אלגוריתם קירוב עם יחס קירוב חסוםBPPפתירות בזמן פולינומי על ידי אלגוריתם אקראי (תשובה נכונה בהסתברות גבוהה)BQPפתירות בזמן פולינומי באמצעות מחשב קוונטי (תשובה נכונה בהסתברות גבוהה)co-NPתשובות "לא" ניתנות לאימות בזמן פולינומי במכונה לא-דטרמיניסטיתco-NP-completeהבעיות הקשות ביותר ב-co-NP((DSPACE(f(nפתירות באמצעות מכונה דטרמיניסטית במקום ((O(f(n.((DTIME(f(nפתירות באמצעות מכונה דטרמיניסטית בזמן ((O(f(n.Eפתירות בזמן אקספוננציאלי עם מעריך ליניאריELEMENTARYאיחוד המחלקות בהיררכיה האקספוננציאליתESPACEפתירות תוך שימוש בזיכרון אקספוננציאלי עם מעריך ליניאריEXPכמו EXPTIMEEXPSPACEפתירות במקום אקספוננציאליEXPTIMEפתירות בזמן אקספוננציאליFNPהאנלוגיה של NP לבעיות פונקציהFPהאנלוגיה של P לבעיות פונקציהFPNPהאנלוגיה של PNP לבעיות פונקציה; בעיית ביתו של הסוכן הנוסעIPפתירות בזמן פולינומי באמצעות מערכת הוכחה אינטראקטיביתLפתירות תוך שימוש במקום לוגריתמי (מעט זיכרון) LOGCFLניתנות לרדוקציית-מקום-לוגריתמי לשפה חופשית הקשרMAפתירות בזמן פולינומי באמצעות פרוטוקול מרלין-ארתור (מערכת הוכחה אינטראקטיבית)NCפתירות באופן יעיל (זמן פולי-לוגריתמי) בחישוב מקבילי.NEפתירות על ידי מכונה לא-דטרמיניסטית בזמן אקספוננציאלי עם מעריך ליניאריNESPACEפתירות על ידי מכונה לא-דטרמיניסטית במקום אקספוננציאלי עם מעריך ליניאריNEXPכמו NEXPTIMENEXPSPACEפתירות על ידי מכונה לא-דטרמיניסטית במקום אקספוננציאליNEXPTIMEפתירות על ידי מכונה לא-דטרמיניסטית בזמן אקספוננציאליNLתשובות "כן" ניתנות לאימות במקום לוגריתמיNONELEMENTARYהמשלימה של ELEMENTARY.NP תשובות "כן" ניתנות לאימות בזמן פולינומי (ראו גם מחלקות סיבוכיות P ו-NP)NP-completeהבעיות הקשות ביותר ב-NPNP-easyהאנלוגיה של PNP לבעיות פונקציה; שם נוסף ל-FPNPNP-equivalentהבעיות הקשות ביותר ב-FPNPNP-hardקשה לפחות כמו כל בעיה ב-NP אבל לא ידוע אם נמצאת באותה מחלקת סיבוכיות((NSPACE(f(nפתירות באמצעות מכונה לא-דטרמיניסטית במקום ((O(f(n.((NTIME(f(nפתירות באמצעות מכונה לא-דטרמיניסטית בזמן ((O(f(n.Pפתירות בזמן פולינומיP-completeבעיות ב-P הקשות ביותר לפתרון במחשוב מקבילי.P/polyפתירות בזמן פולינומי בהינתן "מחרוזת עצה" התלויה אך ורק באורך הקלטPCPמערכת הוכחה מסוג PCP (הוכחה הניתנת לאימות הסתברותי)PHאיחוד המחלקות בהיררכיה הפולינומיתPNPפתירות בזמן פולינומי עם גישת אורקל לבעיה ב-NP; מכונה גם Δ2PPPפתירות באמצעות אלגוריתם הסתברותי בזמן פולינומי (תשובה נכונה בהסתברות גדולה במעט מ-½)PRפתירות באמצעות בניה רקורסיבית של פונקציות אריתמטיותPSPACEפתירות במקום פולינומי.PSPACE-completeהבעיות הקשות ביותר ב-PSPACE.PTASסכמת קירוב זמן-פולינומי (תת מחלקה של APX).Rפתירות תוך זמן סופי.REבעיות עליהן ניתן לענות "כן" תוך זמן סופי, אבל ייתכן שהתשובה "לא" לעולם לא תגיע.RLפתירות תוך שימוש במקום לוגריתמי באמצעות אלגוריתם רנדומי (תשובה "לא" נכונה בהסתברות גבוהה, "כן" נכונה בוודאות).RPפתירות בזמן פולינומי באמצעות אלגוריתם רנדומי (תשובה "לא" נכונה בהסתברות גבוהה, "כן" נכונה בוודאות).SLבעיות הניתנות לרדוקציית-מקום-לוגריתמי לבעיית הקישוריות בין 2 קודקודים נתונים בגרף לא מכוון (להחליט האם קיים מסלול ביניהם). באוקטובר 2004 התברר שהמחלקה למעשה שקולה ל-L.ZPLZPP פתירות באמצעות אלגוריתמים רנדומיים (תשובה נכונה תמיד, סיבוכיות הזיכרון הממוצע לוגריתמית)ZPPפתירות באמצעות אלגוריתמים רנדומיים מסוג לאס-וגאס (תשובה נכונה תמיד, זמן ממוצע פולינומי)

 קישורים חיצוניים 
 Complexity Zoo  - רשימה של מעל 400 מחלקות סיבוכיות והמאפיינים שלהן.

 הערות שוליים 

קטגוריה:מחלקות סיבוכיות
מחלקות סיבוכיות