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

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

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

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

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

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