بيسبايس

☰ جدول المحتويات

نبذة تمهيدية
تعريف
اقسام موجودة في PSAPCE
امثلة
مسائل كاملة
مقالات ذات صلة
مراجع

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

تعريف

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

نقول أنَّ 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)²
${\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 . عادة ما تعتبر المسائل الكاملة هي ممثلة قسم التعقيد الذي تتعبه وهي حتما اهمها .

مراجع

Rahul Jain; Zhengfeng Ji; Sarvagya Upadhyay; John Watrous (July 2009). "QIP = PSPACE". arXiv:.
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:. Bibcode:2009RSPSA.465..631A. doi:10.1098/rspa.2008.0350.
S. Aaronson (March 2005). "NP-complete problems and physical reality". SIGACT News. arXiv:.