بيسبايس

قسم تعقيد

• نظرية التعقيد الحسابي.
• مسألة P=NP
• خوارزمية

تعريف

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

proof system).

من جهة ثانية، مساواة أخرى هي: PSPACE=co-PSPACE , وهذا نابع من مبرهنة Immerman–Szelepcsényi .

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

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

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

في هذا الإطار، من مبرهنة SAVITCH ينبع أنَّ PSPACE=NPSPACE , لذا يمكن ان نبدل التعريف الأول بحيث أنَّ آلة تيورنج الآن هي غير حتمية.

امثلة

في هذا الإطار، اللغة TQBF : وهي لغة كل الصيغ المكممة (quantified boolean formula) التي هي حقيقية. هذه اللغة في PSPACE .

تحديد المنتصر في عدة العاب مثل: GO,chess,draughts ...

كذلك، اللغة : وهي لغة كل الالات المحدودة الحالات غير قطعية التي لغتها هي .

مسائل كاملة

انظر كذلك

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

اقسام موجودة في PSAPCE

علاوةً على ذلك، , هذا الاحتواء نابع من انه يمكن حل مسألة الاكتفاء بواسطة آلة تيورنج حتمية سعة مواردها حدودي وبما ان مسألة الاكتفاء كاملة لذا كل لغة في NP كذلك في PSPACE .

وفي هذا الصدد، هذا ينبع من مبرهنة Sipser–Lautemann والتي بحسبها: وبما أنَّ من هذا ينبع بسهولة أنَّ .

إضافةً إلى ذلك، وذلك لأنَّ PH تُعرف بالشكل التالي: في حين أنَّ هي: نقول أنَّ L تابعة ل- إذا يوجد آلة تيورنج قطعية حدودية، M , بحيث أنَّ:

.

في حين أنَّ:

إضافةً إلى ذلك، وذلك لان كل آلة تيورنج التي زمنها حدودي لا يُمكن ان تستعمل موارد أكثر من زمن اللازم لحساباتها.

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

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

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