مسائل PSPACE كاملة

معطى: تعبير نمطي (R ,(regular expression

• المُخرج: هل R يولد جميع السلاسل؟ أي هل *L(R) = Σ
• انظر كذلك
• نظرية التعقيد الحسابي
• مبرهنة سافيتش
• قسم تعقيد
• مسألة P=NP
• خوارزمية

نقاش

من جانب آخر، ولكن المسالة النموذجية في PSPACE كاملة بشكل عام هي مسألة الصيغ المنطقية المكممة (التي عادة ما يتم اختصارها إلى "QBF" أو "TQBF" يشير حرف "T" إلى صحيحة أو حقيقة) وهذا على غرار المسألة SAT التي هي NP كاملة.

من جانب آخر، أول مسألة بيسبايس كاملة هي مسألة التقرير النحو الحساس للسياق القطعي.ومسألة التقرير للنحو الحساس للسياق ونريد أن نحدد ما إذا كان من الممكن للجملة المعطاة أن تُنتج عن طريق التحولات المُعرفة بواسطة هذا النحو.

إضافةً إلى ذلك، وفي عام 1970، أظهرت نظرية سافيتش أن PSPACE=NPSPACE الأمر الذي يعني أن حتى القواعد النحوية الحساسة للسياق القطعية هي تابعة للقسم PSPACE.

في هذا الإطار، أمثلة الألعاب التي هي PSPACE كاملة (عندما نعمم اللعبة لتكون على لوح بكبر nxn) هي لعبة هيكس ولعبة ريفيرسي ولعبة سوليتير. بعض الألعاب الأخرى المعممة، مثل لعبة الشطرنج ولعبة الرسم ذو المربعات (الدراما) وجو هي EXP كاملة لأن اللعبة بين اثنين من العابين المهرة من الممكن أن يستمر لفترة طويلة جدًا، لذلك فأنهم من غير المحتمل أن يتبعوا PSPACE . ولكن هذه المسائل PSPACE كاملة إذا حددنا عدد الحركات المسموح بها ليكون محدود بواسطة كثير حدود.

كذلك، والدليل على أن مسألة الصيغ المنطقية المكممة "QBF" هي مسألة PSPACE كاملة هي إعادة ترتيب لمُبرهنة SAVITCH وهي لحد كبير أكثر تقنية.

Computational Complexity of Games and Puzzles

Go/Baduk, Board game: "Ladders" work in this way

استراتيجيات الفوز في الألعاب

إضافةً إلى ذلك، انظر إلى التعقيد الألعاب لأغلب الألعاب التي لها تكامل في «بيسبايس» أو صيغ التعقيد الأخرى التي تم تحديدها.

الجغرافيا المعممة

مسألة الصيغ المنطقية المُكممة الصحيحة TQBF

من جهة ثانية، مسألة الصيغ المنطقية المُكممة هي باعطائنا صيغة بوليانية مُكممة (quantified boolean formula) هل هي صحيحة؟ بشكل رسمي هي المجموعة التالية والتي نرمز لها ب- TQBF :

TQBF = : هي صيغة بوليانية مُكممة صحيحة

أمثلة على مسائل بيسبايس كاملة

في هذا الإطار، التالي هو بعض مسائل بيسبايس كاملة مع المخطط التمهيدي للحساب الذي يعرض أنهم في «بيسبايس». ويمكن أن العثور على أغلب الأمثلة في قائمة مسائل «بيسبايس كاملة».

في المدخل

• إذا لم يكن لحرف بي حافة منتهية، أو رفضها.
• وإلا إزالة حرف بي وجميع حوافه، ونسميه الرسم البياني الجديد جي 1.
• مدخلات التشغيل بشكل متكرر ، حيث أن كل بي، تعتبر نقط نهاية الحواف من بي.

الرفض إذا تم قبول الجميع، أو القبول

من جهة ثانية، استخدام المسافة: تعتبر عدد مستويات التكرار مساوية لعدد نقطة اللقاء جي. ويعتبر حجم المعلومات المخزنة في كل مستوي من التكرار مساوي لنقط اللقاء في جي. وبذلك يعتبر إجمالي المسافة خطي.2

تحديد ما إذا كان التعبير المنتظم يولد جميع السلاسل