רשימת מחלקות סיבוכיות
זוהי רשימה של מחלקות סיבוכיות בתורת הסיבוכיות.
לרבות ממחלקות אלו יש שותף '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 | סכמת קירוב זמן-פולינומי (תת מחלקה של APX). | |
| R | פתירות תוך זמן סופי. | |
| RE | בעיות עליהן ניתן לענות "כן" תוך זמן סופי, אבל ייתכן שהתשובה "לא" לעולם לא תגיע. | |
| RL | פתירות תוך שימוש במקום לוגריתמי באמצעות אלגוריתם רנדומי (תשובה "לא" נכונה בהסתברות גבוהה, "כן" נכונה בוודאות). | |
| RP | פתירות בזמן פולינומי באמצעות אלגוריתם רנדומי (תשובה "לא" נכונה בהסתברות גבוהה, "כן" נכונה בוודאות). | |
| SL | בעיות הניתנות לרדוקציית-מקום-לוגריתמי לבעיית הקישוריות בין 2 קודקודים נתונים בגרף לא מכוון (להחליט האם קיים מסלול ביניהם). באוקטובר 2004 התברר שהמחלקה למעשה שקולה ל-L. | |
| ZPL |
ZPP פתירות באמצעות אלגוריתמים רנדומיים (תשובה נכונה תמיד, סיבוכיות הזיכרון הממוצע לוגריתמית) | |
| ZPP | פתירות באמצעות אלגוריתמים רנדומיים מסוג לאס-וגאס (תשובה נכונה תמיד, זמן ממוצע פולינומי) |
קישורים חיצוניים
[עריכת קוד מקור | עריכה]- Complexity Zoo (אורכב 27.08.2019 בארכיון Wayback Machine) - רשימה של מעל 400 מחלקות סיבוכיות והמאפיינים שלהן.
הערות שוליים
[עריכת קוד מקור | עריכה]- ^ Sanjeev Arora, Boaz Barak (2009), Computational Complexity: A Modern Approach, Cambridge University Press; 1 edition, ISBN 978-0-521-42426-4
| מחלקות סיבוכיות חשובות (נוספות) | ||
|---|---|---|
| נחשב מעשי | NL • P • ZPP • RP • BPP • BQP • PTAS • APX | |
| ככל הנראה בלתי מעשי | NP • NP-קשיות • co-NP • PP • #P • PSPACE | |
| נחשב כבלתי מעשי | EXPTIME • NEXPTIME • EXPSPACE • ELEMENTARY • PR • R • RE • ALL | |
| היררכית מחלקות | ההיררכיה הפולינומית • ההיררכיה האקספוננציאלית • ההיררכיה הבוליאנית • ההיררכיה האריתמטית • היררכית גרזגרצ'יק | |
| משפחות של מחלקות | מערכת הוכחה אינטראקטיבית • DTIME • NTIME • DSPACE • NSPACE | |