EXPSPACE

בתורת הסיבוכיות, המחלקה $EXPSPACE$ היא קבוצת כל בעיות ההכרעה הפתירות על ידי מכונת טיורינג דטרמיניסטית ב $O(2^{P(n)})$ במַקום, כאשר $P(n)$ מייצג פונקציה פולינומית של $n$. (מקצת החוקרים מגבילים את $P(n)$ להיות פונקציה ליניארית) לחלופין, אם אנו משתמשים במכונת טיורינג לא דטרמיניסטית, אנחנו מקבלים את המחלקה $NEXPSPACE$, אשר שווה ל-$EXPSPACE$ על ידי משפט סביץ'. $EXPSPACE$ במונחים של $DSPACE$ ו $NSPACE$:

$𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤=\bigcup _{k\in \mathbb{N}}𝖣𝖲𝖯𝖠𝖢𝖤(2^{n^k})=\bigcup _{k\in \mathbb{N}}𝖭𝖲𝖯𝖠𝖢𝖤(2^{n^k})$

EXPSPACE-Complete

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

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

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