برنامج PSPACE-complete

بالنظر إلى تعبير نمطي${\displaystyle R}$تحديد ما إذا كانت الآلة تولد كل سلسلة على أبجديتها هو مسألة كاملة في فضاء PSPACE. ^{[ 6 ]} ويتم البرهان عن طريق أخذ آلة تورينج${\displaystyle M}$وكمية مساحة مشفرة أحادية${\displaystyle n}$وبناء تعبير نمطي يقبل سلسلة نصية إذا وفقط إذا فشل في ترميز تسلسل صحيح من حالات${\displaystyle M}$يبدأ ذلك عند${\displaystyle M}$التكوين الابتدائي وينتهي في${\displaystyle M}$قبول مدخلاتها، على الأكثر${\displaystyle n}$يتم زيارة خلايا الشريط.

كانت أول مسألة معروفة كاملة في فضاء PSPACE هي مسألة الكلمات للقواعد النحوية الحساسة للسياق الحتمية . في هذه المسألة، تُعطى مجموعة من التحويلات النحوية التي يمكنها زيادة طول الجملة، ولكن لا يمكنها إنقاصه، والمطلوب هو تحديد ما إذا كان من الممكن إنتاج جملة معينة باستخدام هذه التحويلات. يضمن الشرط التقني لـ "الحتمية" (والذي يعني تقريبًا أن كل تحويل يُظهر بوضوح استخدامه) إمكانية حل هذه العملية في فضاء متعدد الحدود، وقد أثبت كورودا (1964) أن أي برنامج (قد يكون غير حتمي) قابل للحساب في فضاء خطي يمكن تحويله إلى تحليل نحوي لقاعدة نحوية حساسة للسياق، بطريقة تحافظ على الحتمية. ^{[ 7 ]} في عام 1970، أثبتت نظرية سافيتش أن فضاء PSPACE مغلق تحت عدم الحتمية، مما يعني أن حتى القواعد النحوية الحساسة للسياق غير الحتمية تنتمي إلى فضاء PSPACE. ^{[ 1 ]}

تُعدّ مسألة الصيغة البوليانية الكمية ، وهي تعميم لمسألة قابلية الإرضاء البولياني ، مسألة قياسية كاملة في فضاء PSPACE، وتُستخدم في العديد من نتائج اكتمال فضاء PSPACE الأخرى. تأخذ مسألة الصيغة البوليانية الكمية كمدخل تعبيرًا بوليانيًا، مع تحديد جميع متغيراته كميًا إما بشكل كلي أو وجودي، على سبيل المثال: $${\displaystyle \exists x_{1}\,\forall x_{2}\,\exists x_{3}\,\forall x_{4}:(x_{1}\lor \neg x_{3}\lor x_{4})\land (\neg x_{2}\lor x_{3}\lor \neg x_{4}).}$$ ناتج المسألة هو قيمة التعبير الكمي. إيجاد هذه القيمة مسألة كاملة من فئة PSPACE. ^{[ 1 ]}

تتعلق مسائل إعادة التشكيل باتصال فضاء حالات حلول مسألة توافقية. على سبيل المثال، يُعد اختبار إمكانية ربط تلوينين رباعيين لرسم بياني ببعضهما البعض عن طريق تحريكات تُغير لون رأس واحد في كل مرة، مع الحفاظ على تلوين رباعي صالح في كل خطوة، مسألة كاملة من فئة PSPACE، ^{[ 8 ]} على الرغم من إمكانية حل المسألة نفسها للتلوين الثلاثي في ​​وقت متعدد الحدود. ^{[ 9 ]} وهناك فئة أخرى من مسائل إعادة التشكيل، تُستخدم بشكل مشابه للصيغ المنطقية الكمية كأساس لإثباتات اكتمال PSPACE للعديد من المسائل الأخرى في هذا المجال، وتتضمن منطق القيود غير الحتمي ، حيث تكون الحالات عبارة عن اتجاهات لرسم بياني مقيد يخضع لقيود معينة على عدد الحواف التي يجب أن تكون موجهة للداخل عند كل رأس، وحيث تُعكس التحريكات من حالة إلى أخرى اتجاه حافة واحدة. ^{[ 10 ]}

يمكن تفسير مسألة الصيغة البوليانية الكمية على أنها لعبة بين لاعبين، أحدهما مُدقِّق والآخر مُفنِّد. يقوم اللاعبان بتحركات لملء قيم المتغيرات الكمية، بالترتيب الذي تتداخل به، حيث يقوم المُدقِّق بملء المتغيرات الكمية الوجودية، بينما يقوم المُفنِّد بملء المتغيرات الكمية الشاملة. يفوز المُدقِّق إذا أصبحت الصيغة المُملوءة صحيحة، ويفوز المُفنِّد في غير ذلك. تكون الصيغة الكمية صحيحة إذا وفقط إذا كان لدى المُدقِّق استراتيجية رابحة. وبالمثل، فإن مسألة تحديد الفائز أو الخاسر في العديد من الألعاب التوافقية الأخرى تُعتبر كاملة في فضاء PSPACE. أمثلة على الألعاب الكاملة في فضاء PSPACE (عند تعميمها بحيث يمكن لعبها على${\displaystyle n\times n}$تُعدّ لعبتا Hex و Reversi من الألعاب التي تُصنّف ضمن فئة الألعاب ذات اللوحة . بعض الألعاب العامة الأخرى، مثل الشطرنج والداما (الداما) ولعبة Go ، تُصنّف ضمن فئة الألعاب الكاملة من حيث الوقت المُناسب (EXPTIME-complete) لأنّ مباراة بين لاعبين مثاليين قد تستغرق وقتًا طويلاً جدًا، لذا من غير المُرجّح أن تكون ضمن فئة الألعاب الكاملة من حيث المساحة (PSPACE). ولكنّها ستُصبح كاملة من حيث المساحة (PSPACE-complete) إذا تمّ فرض حدّ متعدد الحدود على عدد النقلات. ^{[ 11 ]}

من الممكن أيضاً أن تكون الألغاز التي يلعبها لاعب واحد كاملة من حيث فضاء PSPACE. غالباً ما يمكن تفسير هذه الألغاز على أنها مسائل إعادة تشكيل، ^{[ 10 ]} وتشمل ألعاب السوليتير مثل Rush Hour و Mahjong و Atomix و Sokoban ، والحاسوب الميكانيكي Turing Tumble . ^{[ 11 ]}

تعتمد اكتمالية PSPACE على التعقيد كدالة لحجم المدخلات${\displaystyle n}$، في الحد كما${\displaystyle n}$ينمو بلا حدود. الألغاز أو الألعاب ذات عدد محدود من الوضعيات مثل الشطرنج على طاولة تقليدية${\displaystyle 8\times 8}$لا يمكن أن تكون لعبة اللوحة كاملة في فضاء PSPACE، لأنه يمكن حلها في وقت ومساحة ثابتين باستخدام جدول بحث كبير جدًا . لصياغة نسخ كاملة في فضاء PSPACE من هذه الألعاب، يجب تعديلها بطريقة تجعل عدد مواضعها غير محدود، مثل لعبها على${\displaystyle n\times n}$بدلاً من ذلك، تُستخدم اللوحة. في بعض الحالات، كما هو الحال في الشطرنج، تكون هذه الامتدادات اصطناعية.