EXPSPACE

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

{\mathsf {EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(2^{n^{k}})=\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})

EXPSPACE-Complete

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