مسائل PSPACE كاملة

من ويكيبيديا، الموسوعة الحرة
(بالتحويل من بيسبايس-كمبليت)
اذهب إلى: تصفح، ‏ ابحث

في نظرية التعقيد الحسابي، تعتبر مسألة قرار بيسبايس-كاملة ( بالانجليزية : PSPACE-complete ) إذا كانت في قسم تعقيد PSPACE، ويمكن أن تختصر كل مسألة في 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 = \{\left \langle\varphi\right \rangle: هي صيغة بوليانية مُكممة صحيحة \left \langle\varphi\right \rangle \}

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

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

الجغرافيا المعممة[عدل]

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

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

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

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

انظر أيضا[عدل]

مراجع[عدل]

وصلات خارجية[عدل]