ALL (מחלקת סיבוכיות)

בתורת החישוביות והסיבוכיות, המחלקה ALL היא מחלקה אשר מכילה את כל בעיות ההכרעה.

יחסים בין המחלקה למחלקות אחרות

המחלקה ALL מכילה את כל מחלקות הסיבוכיות של בעיות ההכרעה, ביניהן גם RE ו-coRE.

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

קישורים חיצוניים

• סקוט אהרונסון, Class ALL, באתר Complexity Zoo (באנגלית)

ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.