پیچیدگی فضا

معبار DSPACE برای تعریف رده پیچیدگی، مجموعه‌ای مسئله‌های تصمیم که با مقدار معینی از از فضای حافظه قابل حل استند، استفاده می‌شود.

معیار DSPACE همتای قطعی NSPACE (رده منبع رایانشی در یک ماشین تورینگ غیرقطعی)است. بر اساس Savitch's theorem, می‌توان گفت:

${\displaystyle {\mathsf {DSPACE}}[s(n)]\subseteq {\mathsf {NSPACE}}[s(n)]\subseteq {\mathsf {DSPACE}}[(s(n))^{2}].}$

NTIME به روش زیر با DSPACE مرتبط است:

${\displaystyle {\mathsf {NTIME}}(t(n))\subseteq {\mathsf {DSPACE}}(t(n))}$

.

• Szepietowski, Andrzej (1994). Turing Machines with Sublogarithmic Space. Springer Science+Business Media. ISBN 978-3-540-58355-4.
• Arora, Sanjeev; Barak, Boaz (2009). Computational complexity. A modern approach. Cambridge University Press. ISBN 978-0-521-42426-4. Zbl 1193.68112.