في نظرية التعقيد القسم PH هو قسم كل اللغات في هرم متعدد الحدود (Polynomial hierarchy)، وهذا القسم يشمل جزء لا بأس به من الاقسام المعروفة مثل: NP ,co-NP ... وله عدة تعريفات متكافئة.
نعرف الاقسام التالية: Σ 1 = NP {\displaystyle \Sigma _{1}={\mbox{NP}}} وبطريقة البناء عن طريق الاستقراء نعرف: Σ i = NP Σ i − 1 {\displaystyle \Sigma _{i}={\mbox{NP}}^{\Sigma _{i-1}}} في حين أنَّ: NP C {\displaystyle {\mbox{NP}}^{C}} هي مجموعة اللغات التي يمكن تقريرها بواسطة آلة تيورنج كثيرة الحدود غير قطعية مع امكانية الدخول إلى اوراكل من القسم C . حينها: PH = ∪ i = 0 ∞ Σ i {\displaystyle {\mbox{PH}}=\cup _{i=0}^{\infty }\Sigma _{i}} 2. نعرف القسم Σ i {\displaystyle \Sigma _{i}} بشكل اخر: L ∈ Σ i {\displaystyle {\mbox{L}}\in \Sigma _{i}} إذا يوجد علاقة محدودة بكثير حدود وقابلة للتمييز بوقت كثير الحدود مع i+1 متغيرات حيث أنَّ: x ∈ L ⟺ ∃ y 1 ∀ y 2 ⋯ Q i y i ( x , y 1 , y 2 , ⋯ , y i ) ∈ R L {\displaystyle x\in L\iff \exists y_{1}\forall y_{2}\cdots Q_{i}y_{i}(x,y_{1},y_{2},\cdots ,y_{i})\in R_{L}} في حين أنَّ Q i = { ∀ , if i is even ∃ , if i is odd {\displaystyle Q_{i}={\begin{cases}\forall ,&{\mbox{if }}i{\mbox{ is even}}\\\exists ,&{\mbox{if }}i{\mbox{ is odd}}\end{cases}}}
يمكن ان نبين أنَّ التعريفان متكافئان وذلك بواسطة الاستقراء لكل i .
على غرار co-NP , P يمكن تعريف اقسام مشابهة وهي:
Δ 1 = P {\displaystyle \Delta _{1}={\mbox{P}}} Δ i = P Δ i − 1 {\displaystyle \Delta _{i}={\mbox{P}}^{\Delta _{i-1}}} Π 1 = co-NP {\displaystyle \Pi _{1}={\mbox{co-NP}}} Π i = co-NP Π i − 1 {\displaystyle \Pi _{i}={\mbox{co-NP}}^{\Pi _{i-1}}} ويمكن تعريف PH بواسطة Δ i {\displaystyle \Delta _{i}} أو بواسطة Π i {\displaystyle \Pi _{i}} وذلك لانَّ:
Π i ⊆ Σ i + 1 {\displaystyle \Pi _{i}\subseteq \Sigma _{i+1}} Σ i ⊆ Π i + 1 {\displaystyle \Sigma _{i}\subseteq \Pi _{i+1}} Σ i ∪ Π i ⊆ Δ i ⊆ Σ i + 1 ∩ Π i + 1 {\displaystyle \Sigma _{i}\cup \Pi _{i}\subseteq \Delta _{i}\subseteq \Sigma _{i+1}\cap \Pi _{i+1}} نقول أنَّ PH انهارت إذا تحقق التالي:
يوجد k بحيث أنَّ Σ k = Σ k + 1 {\displaystyle \Sigma _{k}=\Sigma _{k+1}}
حيث أنه إذا وجد k كهذا حينها: Σ k = PH {\displaystyle \Sigma _{k}={\mbox{PH}}} واغلب علماء الحاسوب والرياضيات يقولون بعدم انهيار الهرم كثير الحدود، ومع هذا فإنه غير معلوم إذا ما PH مُنهار أو لا !
علاقات مع اقسام أخرى[ عدل ] يمكن بسهولة تبيين أنَّ PH ⊆ PSPACE {\displaystyle {\mbox{PH}}\subseteq {\mbox{PSPACE}}} . وذلك لاننا يمكننا تجربة كل الامكانيات كما في تعريف PH ونستخدم مساحة اضافية متعددة الحدود. إذا NP = coNP {\displaystyle {\mbox{NP}}={\mbox{coNP}}} حينها PH=NP {\displaystyle {\mbox{PH=NP}}} لكل i إذا Σ i = Π i {\displaystyle \Sigma _{i}=\Pi _{i}} حينها PH = Σ i {\displaystyle {\mbox{PH}}=\Sigma _{i}} مبرهنة سبسر ولوتومان: BPP ⊆ PH {\displaystyle {\mbox{BPP}}\subseteq {\mbox{PH}}} إذا NP ⊆ P/Poly {\displaystyle {\mbox{NP}}\subseteq {\mbox{P/Poly}}} حينها: Σ 2 = Π 2 {\displaystyle \Sigma _{2}=\Pi _{2}} أي انه PH = Σ 2 {\displaystyle {\mbox{PH}}=\Sigma _{2}} . مبرهنة كانان: لكل k، Σ 2 {\displaystyle \Sigma _{2}} لا يتبع القسم: (Size (nk مبرهنة تودا: PH ⊆ P # P {\displaystyle {\mbox{PH}}\subseteq P^{\#P}} لكل Σi يمكن تعريف المسألة التالية: Σi SAT :
المعطى: صيغة φ ( x,y ) {\displaystyle \varphi ({\mbox{x,y}})} والتي هي بشكل SAT
المخرج: هل صحيح أنَّ: ∃ x ∀ y 1 ∃ y 2 ⋯ Q i y i φ ( x , y 1 , ⋯ , y i ) {\displaystyle \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 = { ∀ , if i is even ∃ , if i is odd {\displaystyle Q_{i}={\begin{cases}\forall ,&{\mbox{if }}i{\mbox{ is even}}\\\exists ,&{\mbox{if }}i{\mbox{ is odd}}\end{cases}}}
هذه المسألة كاملة ل- Σ i {\displaystyle \Sigma _{i}} . يمكن ايجاد مسائل أخرى كاملة [ 1] في الهامش.
لنفرض أن المسألة L هي كاملة في PH ، حينها يوجد k بحيث أنَّ L ∈ Σ k {\displaystyle {\mbox{L}}\in \Sigma _{k}} وبما أن هذه المسألة كاملة كل مسألة في PH يمكن اختزالها لهذه المسألة أي L ومن ضمن هذه المسائل نأخذ المسائل التي تتبع Σ k + 1 {\displaystyle \Sigma _{k+1}} حينها كل مسألة كهذه تتبع أيضا Σ k {\displaystyle \Sigma _{k}} وهذا يعني أنَّ Σ k + 1 ⊆ Σ k {\displaystyle \Sigma _{k+1}\subseteq \Sigma _{k}} وهذا يعني أنَّ P H = Σ k {\displaystyle PH=\Sigma _{k}} وهذا يعني أنَّ الهرم كثير الحدود ينهار ! لذا لا يمكن أن يكون هنالك مسائل كاملة الا إذا انهار PH . وهذا يعطي دليلا أنَّ PH و-PSPACE لا يمكن ان يكونا متساويتيين!
أقسام التعقيد المهمة
ممكنة للتنفيذ مشكوك في إمكانية تنفيذها غير قابل للتنفيذ أقسام هرمية عائلات اقسام