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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

في نظرية التعقيد الحسابي الصنف PH هو توحيد كل الاقسام في هرمية كثيرة الحدود .

لقد تم تعريف هذا القسم لاول مرة بواسطة لاري ستوكماير . وهذا القسم يتبع P#P = PPP وكذلك يتبع PSPACE .

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

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

تعريف[عدل]

 \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}

انظر أيضا[عدل]

Midori Extension.svg هذه بذرة مقالة تحتاج للنمو والتحسين. ساهم في إثرائها بالمشاركة في تحريرها.