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

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

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

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

تعريف

${\displaystyle {\mathcal {PH}}=\cup _{k}\Sigma _{k}^{P}}$ في حين أن ${\displaystyle L\in \Sigma _{k}^{P}}$ إذا يوجد آلة تيورنج كثيرة الحدود قطعية،M, ويوجد متعدد حدود (q(n بحيث أن n هو طول المدخل، ويتحقق: ${\displaystyle 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}$ في حين أنَّ ${\displaystyle Q_{k}={\begin{cases}\forall ,&{\mbox{if }}k{\mbox{ is even}}\\\exists ,&{\mbox{if }}k{\mbox{ is odd}}\end{cases}}}$

مراجع

1. "معلومات عن PH(التعقيد الحسابي) على موقع babelnet.org". babelnet.org. مؤرشف من الأصل في 2020-10-26.

انظر أيضا

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