بيسبايس

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

بيسبايس 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 (July 2009). "QIP = PSPACE". arXiv:0907.4737Freely accessible. 
  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. Bibcode:2009RSPSA.465..631A. arXiv:0808.2669Freely accessible. doi:10.1098/rspa.2008.0350. 
  3. ^ S. Aaronson (March 2005). "NP-complete problems and physical reality". SIGACT News. arXiv:quant-ph/0502072Freely accessible.