عبد العزيز: بوت:صيانة المراجع

2023-03-06T20:51:05Z

بوت:صيانة المراجع

صفحة جديدة

'''بيسبايس''' PSPACE في [[نظرية التعقيد الحسابي]] قسم التعقيد هو قسم كل المسائل التي يمكن حلها بكمية موارد حدودية (polynomial space), هذه المجموعة يُعتقد انها أكبر من NP , ولهذا القسم اهمية كبيرة في حل الألعاب إذ انه مُعظم الألعاب هي PSPACE صعبة ومسألة التقرير لكثير من الألعاب هي PSPACE كاملة.<ref>{{استشهاد بأرخايف|title=QIP = PSPACE|author1=Rahul Jain|author2=Zhengfeng Ji|author3=Sarvagya Upadhyay|author4-link=John Watrous (computer scientist)|author4=John Watrous|arxiv=0907.4737|date=July 2009}}</ref><ref>{{استشهاد بدورية محكمة | doi=10.1098/rspa.2008.0350|bibcode = 2009RSPSA.465..631A | عنوان=Closed timelike curves make quantum and classical computing equivalent | سنة=2009 | الأخير1=Watrous | الأول1=John | الأخير2=Aaronson | الأول2=Scott | صحيفة=Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences | المجلد=465 | العدد=2102 | صفحات=631 |arxiv = 0808.2669 }}</ref><ref>{{استشهاد بدورية محكمة|مؤلف=S. Aaronson | arxiv=quant-ph/0502072| عنوان= NP-complete problems and physical reality |تاريخ=2005-02-21 |مسار=https://archive.org/details/arxiv-quant-ph0502072 |صحيفة=SIGACT News|تاريخ=March 2005}}</ref>

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

هذا هو التعريف الذي منه حصلت المجموعة على اسمها Polynomial Space . وبشكل اخر يمكن كتابة: <math>\mbox{PSPACE}=\bigcup _{c>0} DSPACE(n^c)</math>
* من بعد أن برهن [[عدي شامير]] المبرهنة أنَّ IP=PSPACE يمكن تعريف PSPACE على انها قسم كل اللغات التي يوجد لها نظام برهان تفاعلي (Intractive
proof system).

* من مبرهنة SAVITCH ينبع أنَّ PSPACE=NPSPACE , لذا يمكن ان نبدل التعريف الأول بحيث أنَّ آلة تيورنج الآن هي غير حتمية.
* مساواة أخرى هي: PSPACE=co-PSPACE , وهذا نابع من مبرهنة Immerman–Szelepcsényi .
== اقسام موجودة في PSAPCE ==
PSPACE هي مجموعة مُهمة لاحتوائها كثير من الاقسام المعروفة، ويُظهر هذا قوة هذه المجموعة. والمجموعات الجزئية هي كالتالي:
* <math> \mbox{P} \subseteq \mbox{PSPACE} </math> وذلك لان كل آلة تيورنج التي زمنها حدودي لا يُمكن ان تستخدم موارد أكثر من زمن اللازم لحساباتها.
* <math> \mbox{NP} \subseteq \mbox{PSPACE} </math> , هذا الاحتواء نابع من انه يمكن حل مسألة الاكتفاء بواسطة آلة تيورنج حتمية سعة مواردها حدودي وبما ان مسألة الاكتفاء كاملة لذا كل لغة في NP أيضا في PSPACE .
* <math> \mbox{BPP} \subseteq \mbox{PSPACE} </math> هذا ينبع من مبرهنة Sipser–Lautemann والتي بحسبها: <math> \mbox{BPP} \subseteq \Sigma_2^P</math> وبما أنَّ <math>\Sigma_2^P \subseteq PSPACE </math> من هذا ينبع بسهولة أنَّ <math> \mbox{BPP} \subseteq \mbox{PSPACE} </math> .
* <math> \mbox{PH} \subseteq \mbox{PSPACE} </math> وذلك لأنَّ '''PH''' تُعرف بالشكل التالي: <math> PH=\cup _{k>0} \Sigma_k^P </math> في حين أنَّ <math> \Sigma_k^P</math> هي: نقول أنَّ L تابعة ل-<math> \Sigma_k^P</math> إذا يوجد آلة تيورنج قطعية حدودية، '''M''' , بحيث أنَّ:
<div style="text-align: center;">
<math> 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 </math> </div>

في حين أنَّ: <math> Q_k=\begin{cases}
\exists \ \mbox{if k mod 2 = 1 }\\
\forall \ \mbox{if k mod 2 = 0 }
\end{cases}
</math>

من هذا التعريف يمكن الاستنتاج أنَّ كل مسألة هي مسألة مُبسطة عن المسألة '''TQBF''' لذا فهي بالتالي تابعة ل- '''PSPACE'''
* <math> \mbox{NPSPACE} \subseteq \mbox{PSPACE} </math> هذا نابع من مبرهنة SAVITCH الذي ينص على أنَّ ('''NSPACE'''(T(n))⊆'''SPACE'''(T(n)<sup>2</sup>
* <math> \mbox{P}^{\# P} \subseteq \mbox{PSPACE} </math> .

== امثلة ==
* اللغة TQBF : وهي لغة كل الصيغ المكممة (quantified boolean formula) التي هي حقيقية. هذه اللغة في PSPACE .
* اللغة <math>\mbox{ALL}_\mbox{NFA}</math> : وهي لغة كل [[آلة محدودة الحالات غير قطعية|الالات المحدودة الحالات غير قطعية]] التي لغتها هي <math> \Sigma^*</math> .
* تحديد المنتصر في عدة العاب مثل: [[غو|GO]],[[شطرنج|chess]],[[ضامة|draughts]] ...
== مسائل كاملة ==
{{مفصلة|بيسبايس كاملة}}
مسائل كاملة هي مسائل تابعة ل- PSPACE ويتحقق التالي: يمكن اختصار كل مسألة في PSPACE لهذه المسألة أي انه إذا يمكننا ان نحل هذه المسألة حينها نفس الحل يكون حل لكل المسائل في PSPACE , ولعل أحد هذه المسائل هي TQBF التي جاء ذكرها انفا، وهذه المسائل يُعتقد انها لا تتبع NP أو أي قسم تعقيد ضمن PSPACE , واهمية هذه المسألة تتجلى في برهان [[عدي شامير]] للمبرهنة IP=PSPACE إذ انه كي يبرهن التساوي ما كان عليه الا ان يبرهن أنَّ TQBF تابع ل-IP . عادة ما تعتبر المسائل الكاملة هي ممثلة قسم التعقيد الذي تتعبه وهي حتما اهمها.

== انظر أيضا ==
* [[قسم تعقيد]]
* [[نظرية التعقيد الحسابي]].
* [[مسألة كثير حدود وكثير حدود غير قطعي|مسألة P=NP]]
* [[خوارزمية]]
== مراجع ==
{{مراجع}}

{{أقسام تعقيد}}
{{شريط بوابات|علم الحاسوب|رياضيات}}

[[تصنيف:أقسام التعقيد الحسابي]]
[[تصنيف:معلوماتية نظرية]]

بيسبايس - تاريخ المراجعة

عبد العزيز: بوت:صيانة المراجع