بيسبايس

من ويكيبيديا، الموسوعة الحرة

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

تعريف[عدل]

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

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

هذا هو التعريف الذي منه حصلت المجموعة على اسمها Polynomial Space . وبشكل اخر يمكن كتابة:

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

proof system).

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

اقسام موجودة في PSAPCE[عدل]

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

  • وذلك لان كل آلة تيورنج التي زمنها حدودي لا يُمكن ان تستخدم موارد أكثر من زمن اللازم لحساباتها.
  • , هذا الاحتواء نابع من انه يمكن حل مسألة الاكتفاء بواسطة آلة تيورنج حتمية سعة مواردها حدودي وبما ان مسألة الاكتفاء كاملة لذا كل لغة في NP أيضا في PSPACE .
  • هذا ينبع من مبرهنة Sipser–Lautemann والتي بحسبها: وبما أنَّ من هذا ينبع بسهولة أنَّ .
  • وذلك لأنَّ PH تُعرف بالشكل التالي: في حين أنَّ هي: نقول أنَّ L تابعة ل- إذا يوجد آلة تيورنج قطعية حدودية، M , بحيث أنَّ:

في حين أنَّ:

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

  • هذا نابع من مبرهنة SAVITCH الذي ينص على أنَّ (NSPACE(T(n))⊆SPACE(T(n)2
  • .

امثلة[عدل]

  • اللغة TQBF : وهي لغة كل الصيغ المكممة (quantified boolean formula) التي هي حقيقية. هذه اللغة في PSPACE .
  • اللغة  : وهي لغة كل الالات المحدودة الحالات غير قطعية التي لغتها هي .
  • تحديد المنتصر في عدة العاب مثل: GO,chess,draughts ...

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

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

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

مراجع[عدل]

  1. ^ Rahul Jain؛ Zhengfeng Ji؛ Sarvagya Upadhyay؛ John Watrous (يوليو 2009). "QIP = PSPACE". arXiv:0907.4737.
  2. ^ 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.
  3. ^ S. Aaronson (مارس 2005). "NP-complete problems and physical reality". SIGACT News. arXiv:quant-ph/0502072.