پیچیدگی فضا

در نگره پیچیدگی رایانشی، پیچیدگی فضا یا 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.