بيسبايس-كمبليت

في نظرية التعقيد الحسابي، تعتبر مشكلة القرار "بيسبايس-كمبليت " PSPACE-complete إذا كانت في فئة التعقيد "بيسبايس"، ويمكن أن تقلل كل مشكلة في "بيسبايس" إلى الوقت متعدد الحدود (أنظر التعقيد الكامل). والمشكلة هي أن (بيسبايس-كمبليت) من الممكن أن ينظر إليها على أنها أصعب المشاكل في "بيسبايس" لأن حل أي من مثل هذه المشاكل يمكن أن يستخدم بسهولة لحل أي مشكلة أخرى في "بيسبايس". ويتم الاشتباه في مثل هذه المشاكل بشكل واسع لتكون خارج صيغ التعقيد الأكثر شهرة "بي" و"أن بي"، ولكن لا يعرف ذلك. ومن المعروف أنها تقع خارج الصيغة الصغيرة "إن سي"، ومنذ ورود "إن سي" في البوليل = دي سبيس (سجل رقم)01، التي وردت بشكل دقيق في "بيسبايس" عن طريق نظرية التسلسل الهرمي في المسافة.

المناقشة

وكانت أول معرفة بمشكلة (بيسبايس-كمبليت) مشكلة الكلمة للقواعد النحوية الحساسة للسياق والمنفصلة عنه. وفي مشكلة الكلمة للقواعد النحوية الحساسة للسياق، أعطيت واحدة لمجموعة من التحولات النحوية التي يمكن تزيد طول الجملة ولا يمكن أن تقلله وتود أن تحدد ما إذا كان من الممكن للجملة المعطاة أن تنتج عن طريق تلك التحولات. الحالة الفنية "للحتمية" (مما يعني تقريبًا أن كل تحويل يجعله واضحًا أن كان يستخدم) ويضمن أن تلك العملية يمكن أن تحل في المساحة متعددة الحدود وأظهرت الصيغ اللغوية في عمل إس. واي. كورودا عام 1964 والروبرت المقيد بالتخطيط أن أي (احتمالية منفصلة عن السياق) للبرنامج المحسوب في الفضاء التخطيطي يمكن أن تتحول إلى إعراب القواعد النحوية الحساسة للسياق، وعلى نحو يحافظ على الحتمية. وفي عام 1970، أظهرت نظرية سافيتش أن "بيسبايس" مغلقة بموجب "عدم الحتمية" الأمر الذي يعني أن حتى القواعد النحوية الحساسة للسياق القطعية يمكن أن تكون في "بيسبايس". ولكن المشكلة النموذجية في (بيسبايس-كمبليت) تؤخذ بشكل عام لتكون مشكلة الصيغ المنطقية المقدرة (التي عادة ما يتم اختصارها إلى "كيو بي إف" أو "تي كيو بي إف" يشير حرف "تي" إلى الحقيقة)، عمومية المشكلة المعروفة أولاً "إن بي كومبليت"، مشكلة قابلية الرضا المنطقية (إس إيه تي). وتعتبر مشكلة قابلية الرضا هي مشكلة ما إذا كانت هناك تحديدات للقيمة الحقيق للمتغيرات التي تجعل التعبير المنطقي حقيقيًا. على سبيل المثال، مثل واحد من مشكلة قابلية الرضا المنطقية (إس إيه تي) سيكون التساؤل ما إذا كان التالي حقيقي:

وتختلف مشكلة الصيغة المنطقية المحددة في السماح لكلا التقدير العالمي والوجودي على قيم المتغيرات.

والدليل على أن مشكلة الصيغ المنطقية المقدرة "كيو بي إف" هي مشكلة (بيسبايس-كمبليت) التي تعتبر ضرورية لإعادة صياغة دليل نظرية سافيتش في لغة المنطق وأقل في التقنية. والملاحظة هي أن مشكلة "إن بي كومبليت" تشابه اللغز النموذجي: وهل هناك طريقة للتوصيل في القيم التي تحل المشكلة؟ تشابه مشكلة (بيسبايس-كمبليت) لعبة: هل هناك بعض الحركات التي يمكنني القيام بها، مثل هذا الحركات التي قد يقوم بها خصمي، ثم هل هناك بعض الحركات التي أقوم بها من أجل الفوز؟ يغير التساؤل محددات الكمية الوجودية والعالمية. وليس من المستغرب أن العديد من الألغاز تتحول إلى "إن بي كومبليت" ومعظم الألعاب تتحول إلى (بيسبايس-كمبليت). أمثلة الألعاب التي تكون "بيسبايس-كمبليت" (عندما تعمم حتى يمكن أن تلعب في لوحة إن × إن) هي الألعاب السداسية والعكسية وألعاب سوليتير في ساعة الذروة والمهجونج أتوميكس وسوكوبان. بعض الألعاب الأخرى المعممة، مثل لعبة الشطرنج ولعبة الرسم ذو المربعات (الدراما) وجو تعتبر "إكسبتيم كومبليت" لأن اللعبة بين اثنين من العابين المهرة من الممكن أن يستمر لفترة طويلة جدًا، لذلك فأنهم من غير المحتمل أن يكونوا "بيسبايس". ولكنهم سوف يصبحوا "بيسبايس كومبليت" إذا طبق تعهد متعدد الحدود بعدد من الحركات. وملاحظة أن تعريف تمام "بيسبايس" قائم على التعقيد المقارب: الوقت الذي يستغرقه لحل مشكلة من الحجم "إن"، في الحد الذي تنمو عنده إن بدون قيد. وهذا يعني أن لعبة مثل الدراما (التي تلعب على لوحة 8 × 8) لا يمكن أن تكون"بيسبايس كومبليت" (وفي الحقيقة يمكن حلها في الوقت والمكان المناسب باستخدام جدول البحث الكبير جدًا). وهذا هو السبب الذي من أجله تم تعديل جميع الألعاب بأن تلعب على لوحة إن × إن بديلة، في بعض الحالات، مثل الشطرنج ومثل هذه الملحقات التي تكون على حد ما مصطنعة ووهمية. ومشكلة أخرى في (بيسبايس-كمبليت) هي مشكلة تحديد ما إذا كان هناك شرعية معطاة لعضو اللغة بتعريف القواعد النحوية المعطاة الحساسة للسياق.

أمثلة على مشاكل "بيسبايس-كمبليت"

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

مشكلة الصيغ المنطقية المقدرة تي كيو بي إف TQBF

• نفترض أن مشكلة الصيغ المنطقية المقدرة "تي كيو بي إف" = [<إف>: صيغة منطقية حقيقة مقدرة بشكل كامل]. في المدخل إف.
• إذا لم يكن هناك محدد للكمية، فأن تقييم وقبول إف يكون حقيقيًا.
• إذا كان إف = pF'، فإنها تقيم بشكل متكرر إف1 [بي =1] وإف1 [بي = 0] وتقبل إذا قبل كلها.
• إذا كان إف = If F= qF'، فإنها تقيم بشكل متكرر إف1 [كيو =1] وإف1 [كيو = 0] وتقبل إذا قبل واحد منهم على الأقل.
• استخدام المسافة: تعتبر عدد مستويات التكرار مساوية لعدد من المتغيرات إف. ويعتبر حجم المعلومات المخزنة في كل مستوي من التكرار ثابت (قيم الصيغة لبي = 0 وبي = 1). وبذلك يعتبر إجمالي المسافة خطي. 2

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

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

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

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

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

أعطي التعبير العادي أر، الذي يحدد ما إذا كان يولد جميع السلاسل (i.e., L(R) = Σ*) تعتبر "بيسبايس-كمبليت".

انظر أيضا

• نظرية التعقيد الحسابي
• مشكلة التفكيك إلى جداء عوامل أولية

مراجع

• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. ‎ Section 8.3: PSPACE-completeness, pp. 283–94.
• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. ‎ Section 7.4: Polynomial Space Completeness, pp. 170–77.

وصلات خارجية

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

قالب:ComplexityClasses

PSPACE-complete]] es:PSPACE-completo ko:PSPACE-완전 pt:PSPACE-completude