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