پیچیدگی فضا

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

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

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

ارتباط با دیگر رده‌های پیچیدگی

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

$𝖣𝖲𝖯𝖠𝖢𝖤[s(n)]\subseteq 𝖭𝖲𝖯𝖠𝖢𝖤[s(n)]\subseteq 𝖣𝖲𝖯𝖠𝖢𝖤[(s(n){)}^2].$

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

$𝖭𝖳𝖨𝖬𝖤(t(n))\subseteq 𝖣𝖲𝖯𝖠𝖢𝖤(t(n))$.

منابع

• الگو:Cite book
• الگو:Cite book