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

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

تعريفعدل

  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 على موقع واي باك مشين.

انظر أيضاعدل