الرئيسيةعريقبحث

هرمية كثيرة الحدود


☰ جدول المحتويات


في نظرية التعقيد القسم PH هو قسم كل اللغات في هرم متعدد الحدود (Polynomial hierarchy) ، وهذا القسم يشمل جزء لا بأس به من الاقسام المعروفة مثل : NP ,co-NP ... وله عدة تعريفات متكافئة .

تعريف

Polynomial time hierarchy.svg
  1. نعرف الاقسام التالية :
  • وبطريقة البناء عن طريق الاستقراء نعرف :
في حين أنَّ : هي مجموعة اللغات التي يمكن تقريرها بواسطة آلة تيورنج كثيرة الحدود غير قطعية مع امكانية الدخول إلى اوراكل من القسم C .
حينها :
2. نعرف القسم بشكل اخر : إذا يوجد علاقة محدودة بكثير حدود وقابلة للتمييز بوقت كثير الحدود مع i+1 متغيرات حيث أنَّ : في حين أنَّ

يمكن ان نبين أنَّ التعريفان متكافئان وذلك بواسطة الاستقراء لكل i .

على غرار co-NP , P يمكن تعريف اقسام مشابهة وهي :

ويمكن تعريف PH بواسطة أو بواسطة وذلك لانَّ :

انهيار PH

نقول أنَّ PH انهارت إذا تحقق التالي :

يوجد k بحيث أنَّ

حيث أنه إذا وجد k كهذا حينها : واغلب علماء الحاسوب والرياضيات يقولون بعدم انهيار الهرم كثير الحدود، ومع هذا فإنه غير معلوم إذا ما PH مُنهار أو لا !

علاقات مع اقسام اخرى

  • يمكن بسهولة تبيين أنَّ . وذلك لاننا يمكننا تجربة كل الامكانيات كما في تعريف PH ونستخدم مساحة اضافية متعددة الحدود .
  • إذا حينها
  • لكل i إذا حينها
  • مبرهنة سبسر ولوتومان :
  • إذا حينها : أي انه .
  • مبرهنة كانان : لكل k، لا يتبع القسم : (Size(nk
  • مبرهنة تودا :

مسائل كاملة في Σi

لكل Σi يمكن تعريف المسألة التالية : ΣiSAT :

المعطى : صيغة والتي هي بشكل SAT

المخرج : هل صحيح أنَّ : حيث أنَّ :

هذه المسألة كاملة ل- . يمكن ايجاد مسائل اخرى كاملة [1] في الهامش .

مسائل كاملة في PH

لنفرض أن المسألة L هي كاملة في PH ، حينها يوجد k بحيث أنَّ وبما أن هذه المسألة كاملة كل مسألة في PH يمكن اختزالها لهذه المسألة اي L ومن ضمن هذه المسائل نأخذ المسائل التي تتبع حينها كل مسألة كهذه تتبع أيضا وهذا يعني أنَّ وهذا يعني أنَّ وهذا يعني أنَّ الهرم كثير الحدود ينهار ! لذا لا يمكن أن يكون هنالك مسائل كاملة الا إذا انهار PH . وهذا يعطي دليلا أنَّ PH و-PSPACE لا يمكن ان يكونا متساويتيين!

هامش

  1. phcom.dvi - تصفح: نسخة محفوظة 12 يوليو 2017 على موقع واي باك مشين.

مقالات ذات صلة



موسوعات ذات صلة :