# بيسبايس

بيسبايس 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
* خوارزمية

## مراجع

* ↑ Rahul Jain؛ Zhengfeng Ji؛ Sarvagya Upadhyay؛ John Watrous (يوليو 2009). "QIP = PSPACE". arXiv:0907.4737.
* ↑ Watrous، John؛ Aaronson، Scott (2009). "Closed timelike curves make quantum and classical computing equivalent". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. ج. 465 ع. 2102: 631. arXiv:0808.2669. Bibcode:2009RSPSA.465..631A. DOI:10.1098/rspa.2008.0350.
* ↑ S. Aaronson (مارس 2005). "NP-complete problems and physical reality". SIGACT News. arXiv:quant-ph/0502072.
* بوابة رياضيات
* بوابة علم الحاسوب