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

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

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

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

تعريف

$\mathcal{P}\mathcal{H}={\cup }_k\underset{k}{\overset{P}{\mathrm{\Sigma }}}$ في حين أن $L\in \underset{k}{\overset{P}{\mathrm{\Sigma }}}$ إذا يوجد آلة تيورنج كثيرة الحدود قطعية،M, ويوجد متعدد حدود (q(n بحيث أن n هو طول المدخل، ويتحقق: $x\in L⟺\mathrm{\exists }{u}_1\in \{0,1{\}}^{q(n)}\mathrm{\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{array}{cc}\mathrm{\forall },& k\text{ is even}\\ \mathrm{\exists },& k\text{ is odd}\end{array}$

انظر أيضا

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