بيسبايس

**بيسبايس** PSPACE في نظرية التعقيد الحسابي قسم التعقيد هو قسم كل المسائل التي يمكن حلها بكمية موارد حدودية (polynomial space), هذه المجموعة يُعتقد انها أكبر من NP , ولهذا القسم اهمية كبيرة في حل الألعاب إذ انه مُعظم الألعاب هي PSPACE صعبة ومسألة التقرير لكثير من الألعاب هي PSPACE كاملة.

## تعريف
يوجد عدة وسائل لتعريف هذه المجموعة ومنها:
* نقول أنَّ L ∈ PSPACE إذا وُجدت آلة تيورنج حتمية M بحيث يتحقق (L=L(M وعدد الاماكن غير الفارغة اثناء حساب M على المُدخل x في شريط العمل على الأكثر (|Poly(|x .

هذا هو التعريف الذي منه حصلت المجموعة على اسمها Polynomial Space . وبشكل اخر يمكن كتابة: \mbox{PSPACE}=\bigcup _{c>0} DSPACE(n^c)
* من بعد أن برهن عدي شامير المبرهنة أنَّ IP=PSPACE يمكن تعريف PSPACE على انها قسم كل اللغات التي يوجد لها نظام برهان تفاعلي (Intractive
proof system).

* من مبرهنة SAVITCH ينبع أنَّ PSPACE=NPSPACE , لذا يمكن ان نبدل التعريف الأول بحيث أنَّ آلة تيورنج الآن هي غير حتمية.
* مساواة أخرى هي: PSPACE=co-PSPACE , وهذا نابع من مبرهنة Immerman–Szelepcsényi .
## اقسام موجودة في PSAPCE
PSPACE هي مجموعة مُهمة لاحتوائها كثير من الاقسام المعروفة، ويُظهر هذا قوة هذه المجموعة. والمجموعات الجزئية هي كالتالي:
*  \mbox{P} \subseteq \mbox{PSPACE}  وذلك لان كل آلة تيورنج التي زمنها حدودي لا يُمكن ان تستخدم موارد أكثر من زمن اللازم لحساباتها.
*  \mbox{NP} \subseteq \mbox{PSPACE}  , هذا الاحتواء نابع من انه يمكن حل مسألة الاكتفاء بواسطة آلة تيورنج حتمية سعة مواردها حدودي وبما ان مسألة الاكتفاء كاملة لذا كل لغة في NP أيضا في PSPACE .
*  \mbox{BPP} \subseteq \mbox{PSPACE}  هذا ينبع من مبرهنة Sipser–Lautemann والتي بحسبها:  \mbox{BPP} \subseteq \Sigma_2^P وبما أنَّ \Sigma_2^P \subseteq PSPACE  من هذا ينبع بسهولة أنَّ  \mbox{BPP} \subseteq \mbox{PSPACE}  .
*  \mbox{PH} \subseteq \mbox{PSPACE}  وذلك لأنَّ **PH** تُعرف بالشكل التالي:  PH=\cup _{k>0} \Sigma_k^P  في حين أنَّ  \Sigma_k^P هي: نقول أنَّ L تابعة ل- \Sigma_k^P إذا يوجد آلة تيورنج قطعية حدودية، **M** , بحيث أنَّ:

 x\in L \iff \exists v_1 \in \{0,1\}^{poly(|x|)} \forall v_2 \in \{0,1\}^{poly(|x|)} \cdots Q_k v_k \in \{0,1\}^{poly(|x|)} M(x,v_1,\cdots,v_k)=1  

في حين أنَّ:  Q_k=\begin{cases}
\exists \  \mbox{if k mod 2 = 1 }\\
\forall \ \mbox{if k mod 2 = 0 }
\end{cases}


من هذا التعريف يمكن الاستنتاج أنَّ كل مسألة هي مسألة مُبسطة عن المسألة **TQBF** لذا فهي بالتالي تابعة ل- **PSPACE**
*  \mbox{NPSPACE} \subseteq \mbox{PSPACE}  هذا نابع من مبرهنة SAVITCH الذي ينص على أنَّ (**NSPACE**(T(n))⊆**SPACE**(T(n)2
*  \mbox{P}^{\# P} \subseteq \mbox{PSPACE}  .

## امثلة
* اللغة TQBF : وهي لغة كل الصيغ المكممة (quantified boolean formula) التي هي حقيقية. هذه اللغة في PSPACE .
* اللغة \mbox{ALL}_\mbox{NFA} : وهي لغة كل الالات المحدودة الحالات غير قطعية التي لغتها هي  \Sigma^* .
* تحديد المنتصر في عدة العاب مثل: GO,chess,draughts ...
## مسائل كاملة

مسائل كاملة هي مسائل تابعة ل- PSPACE ويتحقق التالي: يمكن اختصار كل مسألة في PSPACE لهذه المسألة أي انه إذا يمكننا ان نحل هذه المسألة حينها نفس الحل يكون حل لكل المسائل في PSPACE , ولعل أحد هذه المسائل هي TQBF التي جاء ذكرها انفا، وهذه المسائل يُعتقد انها لا تتبع NP أو أي قسم تعقيد ضمن PSPACE , واهمية هذه المسألة تتجلى في برهان عدي شامير للمبرهنة IP=PSPACE إذ انه كي يبرهن التساوي ما كان عليه الا ان يبرهن أنَّ TQBF تابع ل-IP . عادة ما تعتبر المسائل الكاملة هي ممثلة قسم التعقيد الذي تتعبه وهي حتما اهمها.

## انظر أيضا
* قسم تعقيد
* نظرية التعقيد الحسابي.
* مسألة P=NP
* خوارزمية
## مراجع

تصنيف:أقسام التعقيد الحسابي
تصنيف:علم الحاسوب النظري