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

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

PH يحتوي معظم الاقسام في بيسبايس مثل : NP ,P,Co-NP كما أنه يحوي اقسام تعقيد احتمالية مثل : 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}}}$

مقالات ذات صلة

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

موسوعات ذات صلة :

• موسوعة علم الحاسوب
• موسوعة رياضيات