هرمية كثيرة الحدود
المحتويات
تعريفًا بالموضوع، في نظرية التعقيد القسم PH هو قسم كل اللغات في هرم متعدد الحدود (Polynomial hierarchy)، وهذا القسم يشمل جزء لا بأس به من الاقسام المعروفة مثل: NP ,co-NP ... وله عدة تعريفات متكافئة. ونتناول فيما يلي مزيدًا من التفاصيل.
مسائل كاملة في Σi
لكل Σi يمكن تعريف المسألة التالية: ΣiSAT :
لكل i إذا حينها
- مبرهنة سبسر ولوتومان:
- إذا حينها: أي انه .
- مبرهنة كانان: لكل k، لا يتبع القسم: (Size(nk
- مبرهنة تودا:
انهيار PH
نقول أنَّ PH انهارت إذا تحقق التالي:
المعطى: صيغة والتي هي بشكل SAT
في هذا الإطار، هذه المسألة كاملة ل- . يمكن ايجاد مسائل أخرى كاملة في الهامش.
المخرج: هل صحيح أنَّ: حيث أنَّ:
يوجد k بحيث أنَّ
ومن جهة أخرى، حيث أنه إذا وجد k كهذا حينها: واغلب علماء الحاسوب والرياضيات يقولون بعدم انهيار الهرم كثير الحدود، ومع هذا فإنه غير معلوم إذا ما PH مُنهار أو لا !
مسائل كاملة في PH
انظر كذلك
ومن ناحية أخرى، لنفرض أن المسألة L هي كاملة في PH ، حينها يوجد k بحيث أنَّ وبما أن هذه المسألة كاملة كل مسألة في PH يمكن اختزالها لهذه المسألة أي L ومن ضمن هذه المسائل نأخذ المسائل التي تتبع حينها كل مسألة كهذه تتبع كذلك وهذا يعني أنَّ وهذا يعني أنَّ وهذا يعني أنَّ الهرم كثير الحدود ينهار ! لذا لا يمكن أن يكون هنالك مسائل كاملة الا إذا انهار PH . وهذا يعطي دليلا أنَّ PH و-PSPACE لا يمكن ان يكونا متساويتيين!
هامش
تعريف
حينها:
نعرف الاقسام التالية:
- يمكن ان نبين أنَّ التعريفان متكافئان وذلك بواسطة الاستقراء لكل i .
- على غرار co-NP , P يمكن تعريف اقسام مشابهة وهي:
- ويمكن تعريف PH بواسطة أو بواسطة وذلك لانَّ:
وبطريقة البناء عن طريق الاستقراء نعرف:
علاوةً على ذلك، 2. نعرف القسم بشكل اخر: إذا يوجد علاقة محدودة بكثير حدود وقابلة للتمييز بوقت كثير الحدود مع i+1 متغيرات حيث أنَّ: في حين أنَّ
وفي السياق ذاته، في حين أنَّ: هي مجموعة اللغات التي يمكن تقريرها بواسطة آلة تيورنج كثيرة الحدود غير قطعية مع امكانية الدخول إلى اوراكل من القسم C .
قسم تعقيد
مسألة P=NP
نظرية التعقيد الحسابي.
علاقات مع اقسام أخرى
من جانب آخر، يمكن بسهولة تبيين أنَّ . وذلك لاننا يمكننا تجربة كل الامكانيات كما في تعريف PH ونستعمل مساحة اضافية متعددة الحدود.
إذا حينها
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟