PH(التعقيد الحسابي)

في نظرية التعقيد الحسابي الصنف PH هو توحيد كل الاقسام في هرمية كثيرة الحدود. لقد تم تعريف هذا القسم لأول مرة بواسطة لاري ستوكماير. وهذا القسم يتبع P^#P = P^PP وكذلك يتبع بيسبايس.

PH يحتوي معظم الاقسام في بيسبايس مثل: NP ,P,كو-إن بي كما أنه يحوي اقسام تعقيد احتمالية مثل: BPP , RP , ولكن هناك دلائل على أنَّ BQP لا يتبع PH .

P=NP إذا وفقط إذا PH=P لذا فانه كفاية أن يُبرهن أنَّ P≠PH لكي نبرهن أن P≠NP .

تعريف

${\mathcal {PH}}=\cup _{k}\Sigma _{k}^{P}$ في حين أن $L\in \Sigma _{k}^{P}$ إذا يوجد آلة تيورنج كثيرة الحدود قطعية،M, ويوجد متعدد حدود (q(n بحيث أن n هو طول المدخل، ويتحقق: $x\in L\iff \exists u_{1}\in \{0,1\}^{q(n)}\forall u_{2}\{0,1\}^{q(n)}\cdots Q_{k}u_{k}\in \{0,1\}^{q(n)}M(x,u_{1},u_{2},\cdots ,u_{k})=1$ في حين أنَّ $Q_{k}={\begin{cases}\forall ,&{\mbox{if }}k{\mbox{ is even}}\\\exists ,&{\mbox{if }}k{\mbox{ is odd}}\end{cases}}$

انظر أيضا

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