المحتوى هنا ينقصه الاستشهاد بمصادر، أي معلومات غير موثقة يمكن التشكيك بها وإزالتها.

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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
Question book-new.svg
المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (يناير 2016)

في نظرية التعقيد الحسابي الصنف 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
هذه بذرة مقالة بحاجة للتوسيع. شارك في تحريرها.