المساحة غير الحتمية في نظرية التعقيد الحسابي

المساحة غير الحتمية في نظرية التعقيد الحسابي

في نظرية التعقيد الحسابي، تُعرف المساحة غير الحتمية (Non-deterministic Space)، والتي يُرمز لها اختصاراً بـ NSPACE، بأنها المورد الحسابي الذي يصف كمية ذاكرة التخزين (المساحة) التي تستهلكها آلة تورينج غير الحتمية (Non-deterministic Turing Machine) لحل مسألة معينة. وتعتبر NSPACE المقابل غير الحتمي لفئة المساحة الحتمية (DSPACE).

فئات التعقيد القائمة على NSPACE

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

بناءً على هذا التعريف، يمكن اشتقاق عدة فئات تعقيد أساسية، منها:

• REG: وهي فئة اللغات المنتظمة، وتتساوى فيها المساحة الحتمية وغير الحتمية عند استخدام مساحة ثابتة: REG = DSPACE(O(1)) = NSPACE(O(1)).
• NL: وهي فئة اللغات التي يمكن حلها في مساحة لوغاريتمية غير حتمية: NL = NSPACE(O(log n)).
• CSL: فئة اللغات الحساسة للسياق، وتُعرف بأنها NSPACE(O(n)).
• PSPACE: فئة المساحة متعددة الحدود، وهي اتحاد جميع فئات NSPACE ذات الحدود متعددة الحدود: PSPACE = NPSPACE = ⋃k∈N NSPACE(nk).
• EXPSPACE: فئة المساحة الأسية، وتُعرف بأنها EXPSPACE = NEXPSPACE = ⋃k∈N NSPACE(2nk).

من الناحية النظرية، تنص مبرهنة إيمرمان-سزيليبشيني (Immerman–Szelepcsényi theorem) على أن NSPACE(s(n)) مغلقة تحت المتممة لكل دالة s(n) ≥ log n.

العلاقة مع فئات التعقيد الأخرى

العلاقة مع DSPACE

تعتبر NSPACE النسخة غير الحتمية من DSPACE (المساحة الحتمية). وبناءً على التعريف ومبرهنة سافيتش (Savitch's theorem)، فإن العلاقة بينهما تكون كالتالي:

DSPACE[s(n)] ⊆ NSPACE[s(n)] ⊆ DSPACE[(s(n))2]

العلاقة مع التعقيد الزمني

يمكن استخدام NSPACE أيضاً لتحديد سقف للتعقيد الزمني الحتمي للمسألة. فإذا كانت اللغة L تُحل في مساحة S(n) (حيث S(n) ≥ log n) بواسطة آلة تورينج غير حتمية، فإنه يوجد ثابت C يجعل اللغة L قابلة للحل زمنياً في حدود O(CS(n)) بواسطة آلة حتمية.

القيود والتطبيقات العملية

تكمن أهمية مقياس DSPACE في أنه يمثل كمية الذاكرة الفعلية التي يحتاجها الحاسوب الحقيقي لحل مسألة ما باستخدام خوارزمية معينة، لأن الحواسيب الحالية هي آلات حتمية. في المقابل، تظل NSPACE مفهوماً نظرياً لأن آلات تورينج غير الحتمية لا توجد في الواقع المادي، مما يجعل استخدام NSPACE محدوداً في التطبيقات العملية المباشرة، لكنه يظل أساسياً في فهم حدود الحوسبة وتصنيف المسائل.