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

في نظرية التعقيد القسم **PH** هو قسم كل اللغات في هرم متعدد الحدود (Polynomial hierarchy)، وهذا القسم يشمل جزء لا بأس به من الاقسام المعروفة مثل: NP ,co-NP ... وله عدة تعريفات متكافئة.
## تعريف
تصغير
# نعرف الاقسام التالية:
:*  \Sigma_1=\mbox{NP}
:* وبطريقة البناء عن طريق الاستقراء نعرف: \Sigma_i=\mbox{NP}^{\Sigma_{i-1}}

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

: حينها:  \mbox{PH}=\cup_{i=0}^\infty \Sigma_i 

:2. نعرف القسم \Sigma_i  بشكل اخر:\mbox{L}\in\Sigma_i إذا يوجد علاقة محدودة بكثير حدود وقابلة للتمييز بوقت كثير الحدود مع i+1 متغيرات حيث أنَّ: x\in L \iff \exists y_1 \forall y_2 \cdots Q_iy_i (x,y_1,y_2,\cdots,y_i)\in R_L  في حين أنَّ

 Q_i=\begin{cases} 
\forall,  & \mbox{if }i\mbox{ is even} \\
\exists, & \mbox{if }i\mbox{ is odd} 
\end{cases}


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

على غرار co-NP , P يمكن تعريف اقسام مشابهة وهي:
*  \Delta_1=\mbox{P}
*  \Delta_i=\mbox{P}^{\Delta_{i-1}}
*  \Pi_1=\mbox{co-NP}
*  \Pi_i=\mbox{co-NP}^{\Pi_{i-1}}

ويمكن تعريف PH بواسطة  \Delta_i أو بواسطة \Pi_i وذلك لانَّ:
*  \Pi_i \subseteq \Sigma_{i+1} 
*  \Sigma_i \subseteq \Pi_{i+1} 
*  \Sigma_i \cup \Pi_i \subseteq \Delta_i \subseteq \Sigma_{i+1} \cap \Pi_{i+1}
## انهيار PH
نقول أنَّ PH انهارت إذا تحقق التالي:

يوجد k بحيث أنَّ  \Sigma_k=\Sigma_{k+1} 

حيث أنه إذا وجد k كهذا حينها:  \Sigma_k=\mbox{PH}  واغلب علماء الحاسوب والرياضيات يقولون بعدم انهيار الهرم كثير الحدود، ومع هذا فإنه غير معلوم إذا ما PH مُنهار أو لا !
## علاقات مع اقسام أخرى
* يمكن بسهولة تبيين أنَّ  \mbox{PH}\subseteq \mbox{PSPACE}  . وذلك لاننا يمكننا تجربة كل الامكانيات كما في تعريف PH ونستخدم مساحة اضافية متعددة الحدود.
* إذا  \mbox{NP}=\mbox{coNP}  حينها  \mbox{PH=NP} 
* لكل i إذا  \Sigma_i=\Pi_i  حينها  \mbox{PH}=\Sigma_i
* مبرهنة سبسر ولوتومان: \mbox{BPP}\subseteq \mbox{PH} 
* إذا  \mbox{NP} \subseteq \mbox{P/Poly}  حينها:  \Sigma_2=\Pi_2  أي انه  \mbox{PH}=\Sigma_2  .
* مبرهنة كانان: لكل k،  \Sigma_2  لا يتبع القسم: (**Size**(nk
* مبرهنة تودا:  \mbox{PH}\subseteq  P^{\#P}

## مسائل كاملة في Σ<sub>i</sub>
لكل Σi يمكن تعريف المسألة التالية: ΣiSAT :

المعطى: صيغة  \varphi(\mbox{x,y})  والتي هي بشكل SAT

المخرج: هل صحيح أنَّ:  \exists x \forall y_1 \exists y_2 \cdots Q_i y_i \varphi (\mbox{x},\mbox{y}_1,\cdots,\mbox{y}_i)  حيث أنَّ: 
 Q_i=\begin{cases} 
\forall,  & \mbox{if }i\mbox{ is even} \\
\exists, & \mbox{if }i\mbox{ is odd} 
\end{cases}


هذه المسألة كاملة ل- \Sigma_i  . يمكن ايجاد مسائل أخرى كاملة  في الهامش.
## مسائل كاملة في PH
لنفرض أن المسألة L هي كاملة في PH ، حينها يوجد k بحيث أنَّ  \mbox{L} \in \Sigma_k  وبما أن هذه المسألة كاملة كل مسألة في PH يمكن اختزالها لهذه المسألة أي L ومن ضمن هذه المسائل نأخذ المسائل التي تتبع  \Sigma_{k+1}  حينها كل مسألة كهذه تتبع أيضا  \Sigma_k  وهذا يعني أنَّ  \Sigma_{k+1} \subseteq \Sigma_k  وهذا يعني أنَّ  PH=\Sigma_k  وهذا يعني أنَّ الهرم كثير الحدود ينهار ! لذا لا يمكن أن يكون هنالك مسائل كاملة الا إذا انهار PH . وهذا يعطي دليلا أنَّ PH و-PSPACE لا يمكن ان يكونا متساويتيين!
## هامش

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

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