بيسبايس

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


  • بوابة علم الحاسوب
  • بوابة رياضيات
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.