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$. במילים אחרות, קיים אלגוריתם בעל זמן ריצה פולינומי הממפה איברים מבעיה אחת לשנייה.

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

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

דוגמאות

פרק זה לוקה בחסר. אנא תרמו לוויקיפדיה והשלימו אותו.