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

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

في نظرية التعقيد القسم 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 لا يمكن ان يكونا متساويتيين!

هامش[عدل]

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