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

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

تعريف 

 نعرف الاقسام التالية: 
 
 وبطريقة البناء عن طريق الاستقراء نعرف: 

 في حين أنَّ: هي مجموعة اللغات التي يمكن تقريرها بواسطة آلة تيورنج كثيرة الحدود غير قطعية مع امكانية الدخول إلى اوراكل من القسم C .

 حينها: 

2. نعرف القسم  بشكل اخر: إذا يوجد علاقة محدودة بكثير حدود وقابلة للتمييز بوقت كثير الحدود مع i+1 متغيرات حيث أنَّ:  في حين أنَّ 

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

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

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

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

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

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

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

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

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

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

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

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

هامش

انظر أيضا 
 قسم تعقيد
 نظرية التعقيد الحسابي.
 مسألة P=NP
 خوارزمية

أقسام التعقيد الحسابي
تراتبية
معلوماتية نظرية
منطق رياضي