EXPSPACE

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

$\mathsf{E}\mathsf{X}\mathsf{P}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}=\bigcup _{k\in \mathbb{\mathbb{N}}}\mathsf{D}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}(2^{n^k})=\bigcup _{k\in \mathbb{\mathbb{N}}}\mathsf{N}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}(2^{n^k})$

EXPSPACE-Complete

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

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

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

דוגמאות

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

EXPSPACE41739836Q1141985