بيسبايس

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

تعريف

يوجد عدة وسائل لتعريف هذه المجموعة ومنها:

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

هذا هو التعريف الذي منه حصلت المجموعة على اسمها Polynomial Space . وبشكل اخر يمكن كتابة: $\text{PSPACE}={\bigcup }_{c>0}DSPACE(n^c)$

• من بعد أن برهن عدي شامير المبرهنة أنَّ IP=PSPACE يمكن تعريف PSPACE على انها قسم كل اللغات التي يوجد لها نظام برهان تفاعلي (Intractive

proof system).

• من مبرهنة SAVITCH ينبع أنَّ PSPACE=NPSPACE , لذا يمكن ان نبدل التعريف الأول بحيث أنَّ آلة تيورنج الآن هي غير حتمية.
• مساواة أخرى هي: PSPACE=co-PSPACE , وهذا نابع من مبرهنة Immerman–Szelepcsényi .

اقسام موجودة في PSAPCE

PSPACE هي مجموعة مُهمة لاحتوائها كثير من الاقسام المعروفة، ويُظهر هذا قوة هذه المجموعة. والمجموعات الجزئية هي كالتالي:

• $\text{P}\subseteq \text{PSPACE}$ وذلك لان كل آلة تيورنج التي زمنها حدودي لا يُمكن ان تستخدم موارد أكثر من زمن اللازم لحساباتها.
• $\text{NP}\subseteq \text{PSPACE}$ , هذا الاحتواء نابع من انه يمكن حل مسألة الاكتفاء بواسطة آلة تيورنج حتمية سعة مواردها حدودي وبما ان مسألة الاكتفاء كاملة لذا كل لغة في NP أيضا في PSPACE .
• $\text{BPP}\subseteq \text{PSPACE}$ هذا ينبع من مبرهنة Sipser–Lautemann والتي بحسبها: $\text{BPP}\subseteq \underset{2}{\overset{P}{\mathrm{\Sigma }}}$ وبما أنَّ $\underset{2}{\overset{P}{\mathrm{\Sigma }}}\subseteq PSPACE$ من هذا ينبع بسهولة أنَّ $\text{BPP}\subseteq \text{PSPACE}$ .
• $\text{PH}\subseteq \text{PSPACE}$ وذلك لأنَّ PH تُعرف بالشكل التالي: $PH={\cup }_{k>0}\underset{k}{\overset{P}{\mathrm{\Sigma }}}$ في حين أنَّ $\underset{k}{\overset{P}{\mathrm{\Sigma }}}$ هي: نقول أنَّ L تابعة ل-$\underset{k}{\overset{P}{\mathrm{\Sigma }}}$ إذا يوجد آلة تيورنج قطعية حدودية، M , بحيث أنَّ:

$x\in L⟺\mathrm{\exists }{v}_1\in \{0,1{\}}^{poly(|x|)}\mathrm{\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{array}{c}\mathrm{\exists }\text{if k mod 2 = 1 }\\ \mathrm{\forall }\text{if k mod 2 = 0 }\end{array}$

من هذا التعريف يمكن الاستنتاج أنَّ كل مسألة هي مسألة مُبسطة عن المسألة TQBF لذا فهي بالتالي تابعة ل- PSPACE

• $\text{NPSPACE}\subseteq \text{PSPACE}$ هذا نابع من مبرهنة SAVITCH الذي ينص على أنَّ (NSPACE(T(n))⊆SPACE(T(n)²
• ${\text{P}}^{\#P}\subseteq \text{PSPACE}$ .

امثلة

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

مسائل كاملة

المقالة الرئيسية: بيسبايس كاملة

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

انظر أيضا

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