المحتوى هنا ينقصه الاستشهاد بمصادر، أي معلومات غير موثقة يمكن التشكيك بها وإزالتها.

بيسبايس

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
Question book-new.svg
المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (فبراير 2016)

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

تعريف[عدل]

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

  • نقول أنَّ 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 . عادة ما تعتبر المسائل الكاملة هي ممثلة قسم التعقيد الذي تتعبه وهي حتما اهمها .

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