پیچیدگی فضا

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

رده های پیچیدگی

معبار 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.