EXPSPACE
קפיצה לניווט
קפיצה לחיפוש
בתורת הסיבוכיות, המחלקה היא קבוצת כל בעיות ההכרעה הפתירות על ידי מכונת טיורינג דטרמיניסטית ב במַקום, כאשר מייצג פונקציה פולינומית של . (מקצת החוקרים מגבילים את להיות פונקציה ליניארית) לחלופין, אם אנו משתמשים במכונת טיורינג לא דטרמיניסטית, אנחנו מקבלים את המחלקה , אשר שווה ל- על ידי משפט סביץ'. במונחים של ו :
EXPSPACE-Complete
בעיית הכרעה נחשבת אם היא שייכת ל-, וקיימת לכל בעיה ב- רדוקציה פולינומית אל . במילים אחרות, קיים אלגוריתם בעל זמן ריצה פולינומי הממפה איברים מבעיה אחת לשנייה.
ניתן לחשוב על בעיות כבעיות הקשות ביותר במחלקה .
מכילה ממש את PSPACE, NP, P ורווח בין החוקרים לחשוב כי היא מכילה ממש את EXPTIME.
דוגמאות
פרק זה לוקה בחסר. אנא תרמו למכלול והשלימו אותו.
מחלקות חישוביות וסיבוכיות | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
מחלקות סיבוכיות חשובות (נוספות) | ||
---|---|---|
נחשב מעשי | NL • P • ZPP • RP • BPP • BQP • PTAS • APX | |
ככל הנראה בלתי מעשי | NP • NP-קשיות • co-NP • PP • #P • PSPACE | |
נחשב כבלתי מעשי | EXPTIME • NEXPTIME • EXPSPACE • ELEMENTARY • PR • R • RE • ALL | |
היררכית מחלקות | ההיררכיה הפולינומית • ההיררכיה האקספוננציאלית • ההיררכיה הבוליאנית • ההיררכיה האריתמטית • היררכית גרזגרצ'יק | |
משפחות של מחלקות | מערכת הוכחה אינטראקטיבית • DTIME • NTIME • DSPACE • NSPACE |
EXPSPACE41739836Q1141985