فضاء الذاكرة متعدد الحدود (PSPACE)

فضاء الذاكرة متعدد الحدود (PSPACE)

في نظرية التعقيد الحسابي، يُعرف فضاء الذاكرة متعدد الحدود (PSPACE) بأنه مجموعة كافة مسائل القرار التي يمكن حلها بواسطة آلة تورينج (Turing machine) باستخدام كمية من المساحة (الذاكرة) تكون دالة متعددة الحدود في حجم المدخلات. وبمعنى آخر، لا يهم مقدار الوقت الذي تستغرقه الآلة للوصول إلى الحل، طالما أن الذاكرة المستخدمة لا تتجاوز حدوداً معينة يحددها متعدد حدود.

التعريف الرسمي

إذا رمزنا بـ $\mathsf{SPACE}(f(n))$ مجموعة كافة المسائل التي يمكن حلها بواسطة آلات تورينج باستخدام مساحة قدرها $O(f(n))$ لبعض الدالة $f$ من حجم المدخلات $n$، فإننا نعرف $\mathsf{PSPACE}$ رسمياً على النحو التالي:

من الملاحظات الجوهرية في هذا المجال أن السماح لآلة تورينج بأن تكون غير حتمية (Nondeterministic) لا يضيف قوة حسابية إضافية لهذه الفئة. وذلك بفضل نظرية سافيتش (Savitch's theorem)، التي تثبت أن $\mathsf{NPSPACE}$ تكافئ $\mathsf{PSPACE}$؛ حيث يمكن لآلة تورينج حتمية محاكاة آلة غير حتمية مع تربيع مقدار المساحة المستخدمة تقريباً، وبما أن تربيع متعدد الحدود ينتج عنه متعدد حدود آخر، تظل النتيجة ضمن $\mathsf{PSPACE}$.

كما أن متممات جميع المسائل الموجودة في $\mathsf{PSPACE}$ تقع أيضاً ضمن نفس الفئة، مما يعني أن $\mathsf{coPSPACE} = \mathsf{PSPACE}$.

العلاقة بين PSPACE وفئات التعقيد الأخرى

ترتبط $\mathsf{PSPACE}$ بعدة فئات تعقيد أخرى مثل $\mathsf{NL}$ و $\mathsf{P}$ و $\mathsf{NP}$ و $\mathsf{PH}$ و $\mathsf{EXPTIME}$ و $\mathsf{EXPSPACE}$. وتتلخص هذه العلاقات في التسلسل التالي:

• $\mathsf{NL} \subseteq \mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{PH} \subseteq \mathsf{PSPACE}$
• $\mathsf{PSPACE} \subseteq \mathsf{EXPTIME} \subseteq \mathsf{EXPSPACE}$
• $\mathsf{NL} \subset \mathsf{PSPACE} \subset \mathsf{EXPSPACE}$
• $\mathsf{P} \subset \mathsf{EXPTIME}$

من السطر الثالث، يتضح أن هناك احتواءً صارماً (Strict containment) في بعض هذه العلاقات. ومن المعروف أن $\mathsf{NL}$ هي مجموعة جزئية فعلية من $\mathsf{PSPACE}$، وكذلك $\mathsf{PSPACE}$ هي مجموعة جزئية فعلية من $\mathsf{EXPSPACE}$، وذلك بناءً على نظرية تسلسل المساحة (Space Hierarchy Theorem). ومع ذلك، لا يزال من غير المعروف بدقة أي من الاحتواءات في السطرين الأول والثاني هي الصارمة، رغم أن الاعتقاد السائد بين العلماء هو أن جميعها صارمة.

خصائص الإغلاق والتوصيفات البديلة

تتميز الفئة $\mathsf{PSPACE}$ بأنها مغلقة تحت عمليات الاتحاد، والمتممة، ونجمة كلين (Kleene star). بالإضافة إلى ذلك، هناك عدة طرق بديلة لتوصيف هذه الفئة:

التوصيف عبر آلات تورينج المتناوبة

يمكن تعريف $\mathsf{PSPACE}$ بأنها مجموعة المسائل التي يمكن حلها بواسطة آلة تورينج متناوبة (Alternating Turing machine) في وقت متعدد الحدود، وهو ما يُعرف أحياناً بـ $\mathsf{APTIME}$ أو $\mathsf{AP}$.

التوصيف المنطقي

من منظور نظرية التعقيد الوصفي، $\mathsf{PSPACE}$ هي مجموعة المسائل التي يمكن التعبير عنها في المنطق من الدرجة الثانية مع إضافة عامل الإغلاق المتعدي (Transitive closure operator). هذا العامل هو ما يميز $\mathsf{PSPACE}$ (احتمالاً) عن التسلسل الهرمي متعدد الحدود $\mathsf{PH}$.

أنظمة الإثبات التفاعلية والتعقيد الكمي

أحد أهم النتائج في نظرية التعقيد هو أن $\mathsf{PSPACE}$ تكافئ الفئة $\mathsf{IP}$، وهي مجموعة اللغات التي يمكن التعرف عليها بواسطة نظام إثبات تفاعلي (Interactive Proof System). في هذا النظام، يحاول "مُثبت" (Prover) كلي القدرة إقناع "مُحقق" (Verifier) يعمل في وقت متعدد حدود وعشوائي بأن سلسلة معينة تنتمي إلى اللغة.

علاوة على ذلك، يمكن توصيف $\mathsf{PSPACE}$ أيضاً كفئة تعقيد كمي تُعرف بـ $\mathsf{QIP}$.