EXPSPACE

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

במונחים של  ו :

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

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

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

דוגמאות 

מחלקות סיבוכיות