ALL (מחלקת סיבוכיות)
מחלקת סיבוכיות שמכילה את כל בעיות ההכרעה מוויקיפדיה, האנציקלופדיה החופשית
בתורת החישוביות והסיבוכיות, המחלקה ALL היא מחלקה אשר מכילה את כל בעיות ההכרעה.
המחלקה ALL מכילה את כל מחלקות הסיבוכיות של בעיות ההכרעה, ביניהן גם RE ו-coRE.
כיוון שיש בעיות הכרעה שאינן כריעות עקב בעיית העצירה וקבוצות מכונת הטיורינג שקיימות היא קבוצה בת מנייה, אז לא ניתן לפתור את כל בעיות ההכרעה האלו ובפרט גם לא קיימות שפות שלמות במחלקה הזו.
- סקוט אהרונסון, Class ALL, באתר Complexity Zoo (באנגלית)
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
