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.
דוגמאות
EXPSPACE39416891Q1141985