EXPSPACE

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

בתורת הסיבוכיות, המחלקה היא קבוצת כל בעיות ההכרעה הפתירות על ידי מכונת טיורינג דטרמיניסטית ב במַקום, כאשר  מייצג פונקציה פולינומיאלית של . (מקצת החוקרים מגבילים את  להיות פונקציה ליניארית) לחלופין, אם אנו משתמשים במכונת טיורינג לא דטרמיניסטית, אנחנו מקבלים את המחלקה , אשר שווה ל- על ידי משפט סביץ'. במונחים של ו :

EXPSPACE-Complete[עריכת קוד מקור | עריכה]

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

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

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

דוגמאות[עריכת קוד מקור | עריכה]