EXPSPACE

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

במונחים של  ו :

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

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

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

 דוגמאות 

קטגוריה:מחלקות סיבוכיות