بيسبايس

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

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

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

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

proof system ) .

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

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

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

${\displaystyle 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}$

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

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

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

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

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

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

• بوابة علم الحاسوب
• بوابة رياضيات