دي سبيس

في نظرية التعقيد الحسابي ، يُشير مصطلح DSPACE أو SPACE إلى مورد الذاكرة اللازم لآلة تورينج حتمية . وهو يُمثل إجمالي مساحة الذاكرة التي يحتاجها حاسوب مادي "عادي" لحل مسألة حسابية معينة باستخدام خوارزمية محددة .

يُستخدم مقياس DSPACE لتحديد فئات التعقيد ، وهي مجموعات من جميع مسائل القرار التي يمكن حلها باستخدام مقدار معين من مساحة الذاكرة. لكل دالة f ( n )، توجد فئة تعقيد SPACE( f ( n ))، وهي مجموعة مسائل القرار التي يمكن حلها بواسطة آلة تورينج حتمية باستخدام مساحة O ( f ( n )). لا توجد قيود على مقدار وقت الحساب الذي يمكن استخدامه، على الرغم من أنه قد توجد قيود على بعض مقاييس التعقيد الأخرى (مثل التناوب ).

تُعرَّف عدة فئات تعقيد مهمة بدلالة مساحة البيانات (DSPACE) . وتشمل هذه الفئات ما يلي:

• REG = DSPACE( O (1))، حيث REG هي فئة اللغات المنتظمة . في الواقع، REG = DSPACE( o (log  log n )) (أي أن مساحة Ω(log log n ) مطلوبة للتعرف على أي لغة غير منتظمة). ^{[ 1 ] [ 2 ]}   

البرهان: لنفترض وجود لغة غير منتظمة L ∈ DSPACE( s ( n ))، حيث s ( n ) = o (log log n ). ولتكن M آلة تورينج تقرر L في الفضاء s ( n ). بناءً على فرضيتنا ، L ∉ DSPACE( O (1))؛ وبالتالي، لأي قيمة اختيارية لـ${\displaystyle k\in \mathbb {N} }$، يوجد مدخل M يتطلب مساحة أكبر من k .

ليكن x مدخلاً بأصغر حجم، ويرمز له بـ n، ويتطلب مساحة أكبر من k ، و${\displaystyle {\mathcal {C}}}$لتكن مجموعة جميع تكوينات M على المدخل x . ولأن M ∈ DSPACE( s ( n ))، فإن${\displaystyle |{\mathcal {C}}|\leq 2^{c\cdot s(n)}=o(\log n)}$، حيث c ثابت يعتمد على M.

لنرمز بـ S إلى مجموعة جميع متواليات التقاطع الممكنة للعنصر M على x . لاحظ أن طول متوالية التقاطع للعنصر M على x لا يتجاوز${\displaystyle |{\mathcal {C}}|}$إذا كان أطول من ذلك، فسيتكرر بعض التكوين، وسيدخل M في حلقة لا نهائية. يوجد أيضًا على الأكثر${\displaystyle |{\mathcal {C}}|}$عدد الاحتمالات لكل عنصر من عناصر متتالية التقاطع، لذا فإن عدد متتاليات التقاطع المختلفة لـ M على x هو

${\displaystyle |S|\leq |{\mathcal {C}}|^{|{\mathcal {C}}|}\leq (2^{c\cdot s(n)})^{2^{c\cdot s(n)}}=2^{c\cdot s(n)\cdot 2^{c\cdot s(n)}}<2^{2^{2c\cdot s(n)}}=2^{2^{o(\log \log n)}}=o(n)}$

وفقًا لمبدأ خانة الحمام ، توجد مؤشرات i < j بحيث${\displaystyle {\mathcal {C}}_{i}(x)={\mathcal {C}}_{j}(x)}$، أين${\displaystyle {\mathcal {C}}_{i}(x)}$و${\displaystyle {\mathcal {C}}_{j}(x)}$تمثل هذه التسلسلات المتقاطعة عند الحدود i و j على التوالي.

لنفترض أن x' هي السلسلة الناتجة عن x بحذف جميع الخلايا من i + 1 إلى j . تتصرف الآلة M بنفس الطريقة تمامًا عند إدخال x' كما عند إدخال x ، لذا فهي تحتاج إلى نفس المساحة لحساب x' كما لحساب x . ومع ذلك، فإن | x' | < | x | ، مما يناقض تعريف x . وبالتالي، لا توجد لغة L كما هو مفترض. □

تشير النظرية المذكورة أعلاه إلى ضرورة افتراض الدالة القابلة للإنشاء في الفضاء في نظرية التسلسل الهرمي للفضاء .

• L = DSPACE( O (log n )) 
• مساحة الضغط =${\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(n^{k})}$
• مساحة العبارات =${\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(2^{n^{k}})}$

يُقاس DSPACE تقليديًا على آلة تورينج حتمية . العديد من فئات تعقيد المساحة المهمة هي دون الخطية ، أي أصغر من حجم المدخلات. لذا، فإن "تحميل" الخوارزمية بناءً على حجم المدخلات، أو حجم المخرجات، لن يعكس بدقة مساحة الذاكرة المستخدمة. يُحل هذا الأمر بتعريف آلة تورينج متعددة الأشرطة ذات مدخلات ومخرجات ، وهي آلة تورينج قياسية متعددة الأشرطة، باستثناء أنه لا يمكن الكتابة على شريط المدخلات، ولا يمكن القراءة من شريط المخرجات. يسمح هذا بتعريف فئات مساحة أصغر، مثل L (المساحة اللوغاريتمية)، بدلالة مقدار المساحة المستخدمة بواسطة جميع أشرطة العمل (باستثناء أشرطة المدخلات والمخرجات الخاصة).

بما أنه يمكن دمج العديد من الرموز في رمز واحد بأخذ قوة مناسبة من الأبجدية، فإنه بالنسبة لجميع قيم c ≥ 1 و f بحيث f ( n ) ≥ 1 ، فإن فئة اللغات القابلة للتمييز في فضاء cf ( n ) هي نفسها فئة اللغات القابلة للتمييز في فضاء f ( n ). وهذا يبرر استخدام ترميز Big O في التعريف.

تُظهر نظرية التسلسل الهرمي للفضاء أنه، لكل دالة قابلة للإنشاء في الفضاء${\displaystyle f:\mathbb {N} \to \mathbb {N} }$توجد لغة ما L قابلة للتقرير في الفضاء${\displaystyle O(f(n))}$لكن ليس في الفضاء${\displaystyle o(f(n))}$.

DSPACE هو النظير الحتمي لـ NSPACE ، وهي فئة مساحة الذاكرة على آلة تورينغ غير حتمية . وبحسب نظرية سافيتش ، ^{[ 3 ]} لدينا أن

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

يرتبط NTIME بـ DSPACE بالطريقة التالية. لأيدالة قابلة للإنشاء زمنيًا t ( n )، لدينا

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

تُعرف محاكاة أفضل بكثير للوقت الحتمي : إذا${\displaystyle t(n)\geq n}$،

${\displaystyle {\mathsf {DTIME}}(t(n))\subseteq {\mathsf {DSPACE}}\left({\sqrt {t(n)\log t(n)}}\right)}$

نتيجةً لجهود ويليامز ، ^{[ 4 ]} تحسين حدٍّ أقدم لـ${\displaystyle O(t/\log t)}$بواسطة هوبكروفت ، بول، وفاليانت . ^{[ 5 ]}

من ناحية أخرى، بالنسبة لأي وظيفة${\displaystyle s(n)\geq \log n}$،

${\displaystyle {\mathsf {DSPACE}}(s(n))\subseteq {\mathsf {DTIME}}{\bigl (}2^{O(s(n))}{\bigr )}}$.

• سزيبيتوفسكي، أندريه (1994). آلات تورينج ذات المساحة شبه اللوغاريتمية . سبرينغر ساينس + بيزنس ميديا . ISBN 978-3-540-58355-4.
• أرورا، سانجيف ؛ باراك، بواز (2009). التعقيد الحسابي: منهج حديث . مطبعة جامعة كامبريدج . ISBN 978-0-521-42426-4. Zbl 1193.68112 . 

• حديقة التعقيد : DSPACE( f ( n )) .