مسائل PSPACE كاملة

في نظرية التعقيد الحسابي، مجموعة مسائل التقرير بيسبايس-كاملة (بالإنجليزية: PSPACE-complete) هي مسائل تابعة لقسم التعقيد PSPACE، بحيث يمكن أن تختصر كل مسألة في PSPACE اليها بوقت متعدد الحدود (انظر التعقيد الكامل).

أي هذه المسائل هي المسائل الأصعب في القسم PSPACE من جهة أن حل هذه المسائل بسرعة -أي وقت الخوارزمية متعدد الحدود بالنسبة للمدخل - يفضي لحل كثير من المسائل المشابهة. حَدَسَ العلماء أن مثل هذه المسائل لاتتبع اقسام التعقيد P وNP، ولكن لا نعرف صحة هذا الحدس. ولكنها تقع خارج القسم إن سي، وذلك لأنَّ «إن سي» مجموعة جزئية للقسم $PolyL=DSPACE[\log (n^{O(1)})]$، وهذه القسم الاخير، أي PolyL , مجموعة جزئية فعلية (proper subset) ل-PSPACE .

نقاش

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

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

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

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

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

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

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

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

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

TQBF = $\{⟨\phi ⟩$: هي صيغة بوليانية مُكممة صحيحة $⟨\phi ⟩$ $\}$

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

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

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

• في المدخل <G,b>
• إذا لم يكن لحرف بي حافة منتهية، أو رفضها.
• وإلا إزالة حرف بي وجميع حوافه، ونسميه الرسم البياني الجديد جي 1.
• مدخلات التشغيل بشكل متكرر <G1,bi>، حيث أن كل بي، تعتبر نقط نهاية الحواف من بي.
• الرفض إذا تم قبول الجميع، أو القبول
• استخدام المسافة: تعتبر عدد مستويات التكرار مساوية لعدد نقطة اللقاء جي. ويعتبر حجم المعلومات المخزنة في كل مستوي من التكرار مساوي لنقط اللقاء في جي. وبذلك يعتبر إجمالي المسافة خطي.2

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

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

المُخرج: هل R يولد جميع السلاسل؟ أي هل ^*L(R) = Σ

انظر أيضا

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

مراجع

• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. Section 8.3: PSPACE-completeness, pp. 283–94.
• Michael R. Garey and دايفيد جونسون (عالم) (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. Section 7.4: Polynomial Space Completeness, pp. 170–77.

وصلات خارجية

• Computational Complexity of Games and Puzzles
• Go/Baduk, Board game: "Ladders" work in this way