بيسبايس

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

بيسبايس 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} .

امثلة[عدل]

مسائل كاملة[عدل]

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

أنظر أيضا[عدل]