בתורת הסיבוכיות, המחלקה היא קבוצת כל בעיות ההכרעה הפתירות על ידי מכונת טיורינג דטרמיניסטית ב במַקום, כאשר  מייצג פונקציה פולינומית של . (מקצת החוקרים מגבילים את  להיות פונקציה ליניארית) לחלופין, אם אנו משתמשים במכונת טיורינג לא דטרמיניסטית, אנחנו מקבלים את המחלקה , אשר שווה ל- על ידי משפט סביץ'. במונחים של ו :

EXPSPACE-Complete

עריכה

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

ניתן לחשוב על בעיות   כבעיות הקשות ביותר במחלקה  .

  מכילה ממש את  PSPACE, NP, P ורווח בין החוקרים לחשוב כי היא מכילה ממש את EXPTIME.

דוגמאות

עריכה