بيسبايس

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

تعريف

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

نقول أنَّ 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 .

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

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 \Sigma ^{*$
تحديد المنتصر في عدة العاب مثل : GO,chess,draughts ...

مسائل كاملة

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

انظر أيضا

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

مراجع

^ Rahul Jain; Zhengfeng Ji; Sarvagya Upadhyay; John Watrous (July 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 (March 2005). "NP-complete problems and physical reality". SIGACT News. arXiv:quant-ph/0502072.