ALL (מחלקת סיבוכיות)
בתורת החישוביות והסיבוכיות, המחלקה ALL היא מחלקה אשר מכילה את כל בעיות ההכרעה.
יחסים בין המחלקה למחלקות אחרות
[עריכת קוד מקור | עריכה]המחלקה ALL מכילה את כל מחלקות הסיבוכיות של בעיות ההכרעה, ביניהן גם RE ו-coRE.
כיוון שיש בעיות הכרעה שאינן כריעות עקב בעיית העצירה וקבוצות מכונת הטיורינג שקיימות היא קבוצה בת מנייה, אז לא ניתן לפתור את כל בעיות ההכרעה האלו ובפרט גם לא קיימות שפות שלמות במחלקה הזו.
קישורים חיצוניים
[עריכת קוד מקור | עריכה]- סקוט אהרונסון, Class ALL, באתר Complexity Zoo (באנגלית)
| מחלקות סיבוכיות חשובות (נוספות) | ||
|---|---|---|
| נחשב מעשי | 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 | |
