بي سبيس

مشكلة لم تُحل في علوم الحاسوب

⁠${\displaystyle {\mathsf {P{\overset {?}{=}}PSPACE}}}$⁠

المزيد من المشاكل التي لم يتم حلها في علوم الحاسوب

في نظرية التعقيد الحسابي ، PSPACE هي مجموعة جميع مشاكل القرار التي يمكن حلها بواسطة آلة تورينج باستخدام كمية متعددة الحدود من المساحة .

إذا رمزنا بـ${\displaystyle {\mathsf {SPACE}}(f(n))}$مجموعة جميع المشاكل التي يمكن حلها بواسطة آلات تورينج باستخدام${\displaystyle O(f(n))}$مساحة لبعض الوظائف${\displaystyle f}$حجم الإدخال${\displaystyle n}$ثم يمكننا تعريف${\displaystyle {\mathsf {PSPACE}}}$رسميًا على النحو التالي ^{[ 1 ]}

${\displaystyle {\mathsf {PSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {SPACE}}(n^{k}).}$

اتضح أن السماح لآلة تورينج بأن تكون غير حتمية لا يضيف أي قوة إضافية. وذلك بسبب نظرية سافيتش ، ^{[ 2 ]}${\displaystyle {\mathsf {NPSPACE}}}$يعادل${\displaystyle {\mathsf {PSPACE}}}$لأن آلة تورينغ الحتمية تستطيع محاكاة آلة تورينغ غير الحتمية مع تربيع مقدار المساحة تقريبًا، والتربيع يحوّل كثيرات الحدود إلى كثيرات حدود (أكبر). ^{[ 3 ]} كذلك، فإن مكملات جميع المسائل في${\displaystyle {\mathsf {PSPACE}}}$وهي أيضًا في${\displaystyle {\mathsf {PSPACE}}}$وهذا يعني أن${\displaystyle {\mathsf {coPSPACE}}={\mathsf {PSPACE}}}$[ ^{4 ]​}

العلاقات التالية معروفة بين PSPACE وفئات التعقيد NL و P و NP و PH و EXPTIME و EXPSPACE (نستخدم هنا${\displaystyle \subset }$للدلالة على الاحتواء التام، أي مجموعة جزئية مناسبة، بينما${\displaystyle \subseteq }$(بما في ذلك احتمال أن تكون المجموعتان متطابقتين):

${\displaystyle {\begin{array}{l}{\mathsf {NL\subseteq P\subseteq NP\subseteq PH\subseteq PSPACE}}\\{\mathsf {PSPACE\subseteq EXPTIME\subseteq EXPSPACE}}\\{\mathsf {NL\subset PSPACE\subset EXPSPACE}}\\{\mathsf {P\subset EXPTIME}}\end{array}}}$

يستنتج من السطر الثالث أنه في كل من السطرين الأول والثاني، يجب أن يكون أحد عناصر الاحتواء على الأقل صارمًا، ولكن لا يُعرف أيها. ويُشتبه على نطاق واسع في أن جميعها صارمة.

من المعروف أن شرطي الاحتواء في السطر الثالث شرطان صارمان. الأول ناتج عن القطرنة المباشرة ( نظرية التسلسل الهرمي للفضاء ، NL ⊂ NPSPACE) وحقيقة أن PSPACE = NPSPACE وفقًا لنظرية سافيتش . أما الثاني، فينتج ببساطة من نظرية التسلسل الهرمي للفضاء.

أصعب المسائل في PSPACE هي مسائل PSPACE-complete. راجع PSPACE-complete للاطلاع على أمثلة لمسائل يُشتبه في انتمائها إلى PSPACE ولكنها ليست ضمن NP.

تم إغلاق فئة PSPACE بموجب عمليات الاتحاد والتكامل ونجمة كلين .

يُعدّ وصف PSPACE البديل مجموعة المشكلات التي يمكن حلها بواسطة آلة تورينج المتناوبة في وقت متعدد الحدود، والتي تسمى أحيانًا APTIME أو ببساطة AP. ^{[ 5 ]}

يُمكن وصف PSPACE منطقيًا من منظور نظرية التعقيد الوصفي بأنها مجموعة المسائل التي يُمكن التعبير عنها باستخدام منطق الرتبة الثانية مع إضافة عامل إغلاق متعدٍ . لا يُشترط وجود إغلاق متعدٍ كامل؛ إذ يكفي وجود إغلاق متعدٍ تبادلي، أو حتى أشكال أضعف منه. ولعل إضافة هذا العامل هي ما يُميز PSPACE عن PH .

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

يمكن وصف PSPACE بأنها فئة التعقيد الكمي QIP . ^{[ 6 ]}

تُعادل PSPACE أيضًا P _CTC ، وهي مسائل قابلة للحل بواسطة الحواسيب الكلاسيكية باستخدام منحنيات زمنية مغلقة ، ^{[ 7 ]} وكذلك BQP _CTC ، وهي مسائل قابلة للحل بواسطة الحواسيب الكمومية باستخدام منحنيات زمنية مغلقة. ^{[ 8 ]}

تكون اللغة B كاملة في فضاء PSPACE إذا كانت تنتمي إلى فضاء PSPACE وكانت صعبة في فضاء PSPACE، مما يعني أنه بالنسبة لجميع A ∈ PSPACE،${\displaystyle A\leq _{\text{P}}B}$، أين${\displaystyle A\leq _{\text{P}}B}$يعني ذلك وجود اختزال متعدد الحدود من A إلى B في زمن متعدد الحدود . تُعدّ مسائل PSPACE-complete ذات أهمية بالغة لدراسة مسائل PSPACE لأنها تمثل أصعب المسائل في هذا المجال. إن إيجاد حل بسيط لمسألة PSPACE-complete يعني وجود حل بسيط لجميع المسائل الأخرى في PSPACE، لأن جميع مسائل PSPACE يُمكن اختزالها إلى مسألة PSPACE-complete. ^{[ 9 ]}

ومن الأمثلة على المسائل الكاملة في فضاء PSPACE مسألة الصيغة البولية الكمية (والتي تُختصر عادةً إلى QBF أو TQBF ؛ حيث يرمز الحرف T إلى "صحيح"). ^{[ 9 ]}

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

• باباديميتريو، كريستوس (1993). التعقيد الحسابي (  الطبعة الأولى). أديسون ويسلي. ISBN 0-201-53082-1.الفصل 19: الفضاء متعدد الحدود، الصفحات  455-490.
• سيبسر، مايكل (2006). مقدمة في نظرية الحوسبة (  الطبعة الثانية). تومسون كورس تكنولوجي. ISBN 0-534-95097-3.الفصل الثامن: تعقيد الفضاء
• ويليامز، رايان (2025-02-25). "محاكاة الزمن باستخدام مساحة الجذر التربيعي". arXiv : 2502.17779 [ cs.CC ].

• حديقة حيوانات التعقيد : مساحة P