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

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

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

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

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

#P סופר את מספר הפתרונות של בעיה ב-NP 
#P-complete הבעיות הקשות ביותר ב-#P
2-EXPTIME פתירות בזמן אקספוננט כפול
AC0 מחלקה של סיבוכיות מעגלים עם עומק חסום.
ACC0 מחלקה של סיבוכיות מעגלים עם עומק חסום ושערים מונים.
AC מחלקה של סיבוכיות מעגלים.
AH ההיררכיה האריתמטית.
AP מחלקת הבעיות שניתנות לפתרון בזמן פולינומי באמצעות מכונת טיורינג מתחלפת (ATM)[1]
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 כמו EXPTIME
EXPSPACE פתירות במקום אקספוננציאלי
EXPTIME פתירות בזמן אקספוננציאלי
FNP האנלוגיה של NP לבעיות פונקציה
FP האנלוגיה של P לבעיות פונקציה
FPNP האנלוגיה של PNP לבעיות פונקציה; בעיית ביתו של הסוכן הנוסע
IP פתירות בזמן פולינומי באמצעות מערכת הוכחה אינטראקטיבית
L פתירות תוך שימוש במקום לוגריתמי (מעט זיכרון)
LOGCFL ניתנות לרדוקציית-מקום-לוגריתמי לשפה חופשית הקשר
MA פתירות בזמן פולינומי באמצעות פרוטוקול מרלין-ארתור (מערכת הוכחה אינטראקטיבית)
NC פתירות באופן יעיל (זמן פולי-לוגריתמי) בחישוב מקבילי. 
NE פתירות על ידי מכונה לא-דטרמיניסטית בזמן אקספוננציאלי עם מעריך לינארי
NESPACE פתירות על ידי מכונה לא-דטרמיניסטית במקום אקספוננציאלי עם מעריך לינארי
NEXP כמו NEXPTIME
NEXPSPACE פתירות על ידי מכונה לא-דטרמיניסטית במקום אקספוננציאלי
NEXPTIME פתירות על ידי מכונה לא-דטרמיניסטית בזמן אקספוננציאלי
NL תשובות "כן" ניתנות לאימות במקום לוגריתמי
NONELEMENTARY המשלימה של ELEMENTARY.
NP תשובות "כן" ניתנות לאימות בזמן פולינומי (ראו גם מחלקות סיבוכיות P ו-NP)
NP-complete הבעיות הקשות ביותר ב-NP
NP-easy האנלוגיה של PNP לבעיות פונקציה; שם נוסף ל-FPNP
NP-equivalent הבעיות הקשות ביותר ב-FPNP
NP-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; מכונה גם Δ2P
PP פתירות באמצעות אלגוריתם הסתברותי בזמן פולינומי (תשובה נכונה בהסתברות גדולה במעט מ-½)
PR פתירות באמצעות בניה רקורסיבית של פונקציות אריתמטיות
PSPACE פתירות במקום פולינומי.
PSPACE-complete הבעיות הקשות ביותר ב-PSPACE.
PTAS סכמת קירוב זמן-פולינומי (תת מחלקה של NP). 
R פתירות תוך זמן סופי.
RE בעיות עליהן ניתן לענות "כן" תוך זמן סופי, אבל ייתכן שהתשובה "לא" לעולם לא תגיע.
RL פתירות תוך שימוש במקום לוגריתמי באמצעות אלגוריתם רנדומי (תשובה "לא" נכונה בהסתברות גבוהה, "כן" נכונה בוודאות). 
RP פתירות בזמן פולינומי באמצעות אלגוריתם רנדומי (תשובה "לא" נכונה בהסתברות גבוהה, "כן" נכונה בוודאות).
SL בעיות הניתנות לרדוקציית-מקום-לוגריתמי לבעיית הקישוריות בין 2 קודקודים נתונים בגרף לא מכוון (להחליט האם קיים מסלול ביניהם). באוקטובר 2004 התברר שהמחלקה למעשה שקולה ל-L.
ZPL

ZPP פתירות באמצעות אלגוריתמים רנדומיים (תשובה נכונה תמיד, סיבוכיות הזיכרון הממוצע לוגריתמית)

ZPP פתירות באמצעות אלגוריתמים רנדומיים מסוג לאס-וגאס (תשובה נכונה תמיד, זמן ממוצע פולינומי)

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Sanjeev Arora, Boaz Barak (2009), Computational Complexity: A Modern Approach, Cambridge University Press; 1 edition, ISBN 978-0-521-42426-4 

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

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