EXPSPACE

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

<math>\mathsf{EXPSPACE} = \bigcup_{k\in\mathbb{N}} \mathsf{DSPACE}(2^{n^k}) = \bigcup_{k\in\mathbb{N}} \mathsf{NSPACE}(2^{n^k})</math>

EXPSPACE-Complete

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

ניתן לחשוב על בעיות <math>EXPSPACE-Complete</math> כבעיות הקשות ביותר במחלקה <math>EXPSPACE</math>.

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

דוגמאות

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