EXPSPACE

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

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

EXPSPACE-Complete

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

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

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

דוגמאות

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

מחלקות חישוביות וסיבוכיות

מקרא   מחלקת חישוביות   מחלקת סיבוכיות ${\displaystyle \cap }$ מחלקה המהווה חיתוך של המחלקות שמכילות אותה ומופיעות בתרשים.   מסלול שיורד למטה מצביע על כך שהמחלקה התחתונה היא חלקית ממש למחלקה העליונה   מסלול שיורד למטה מצביע על כך שהמחלקה התחתונה היא חלקית למחלקה העליונה אך לא ידוע האם הן שוות בעיית הכרעה בעיית הכרעה       בעיות כריעות חיובית (למחצה) בעיות כריעות חיובית (למחצה)       בעיות כריעות בעיות כריעות         EXPSPACE EXPSPACE           EXPTIME EXPTIME                                             PSPACE PSPACE                               שפה תלוית הקשר שפה תלוית הקשר   NP NP   BQP BQP co-NP co-NP                                                   BPP BPP                               RP RP co-RP co-RP                       ZPP ZPP ${\displaystyle \,\cap }$                     P P                                 NC NC                   שפה חופשית הקשר שפה חופשית הקשר       שפה רגולרית שפה רגולרית