هرمية كثيرة الحدود

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

في نظرية التعقيد القسم PH هو قسم كل اللغات في هرم متعدد الحدود (Polynomial hierarchy) , وهذا القسم يشمل جزء لا بأس به من الاقسام المعروفة مثل : NP ,co-NP ... وله عدة تعريفات متكافئة .

تعريف[عدل]

Polynomial time hierarchy.svg
  1. نعرف الاقسام التالية :
  •  \Sigma_1=\mbox{NP}
  • وبطريقة البناء عن طريق الاستقراء نعرف : \Sigma_i=\mbox{NP}^{\Sigma_{i-1}}
في حين أنَّ :\mbox{NP}^C هي مجموعة اللغات التي يمكن تقريرها بواسطة الة تيورنج كثيرة الحدود غير قطعية مع امكانية الدخول إلى اوراكل من القسم C .
حينها :  \mbox{PH}=\cup_{i=0}^\infty \Sigma_i
2. نعرف القسم \Sigma_i بشكل اخر :\mbox{L}\in\Sigma_i اذا يوجد علاقة محدودة بكثير حدود وقابلة للتمييز بوقت كثير الحدود مع i+1 متغيرات حيث أنَّ : x\in L \iff \exists y_1 \forall y_2 \cdots Q_iy_i (x,y_1,y_2,\cdots,y_i)\in R_L في حين أنَّ

 Q_i=\begin{cases} 
\forall,  & \mbox{if }i\mbox{ is even} \\
\exists, & \mbox{if }i\mbox{ is odd} 
\end{cases}

يمكن ان نبين أنَّ التعريفان متكافئان وذلك بواسطة الاستقراء لكل i .

على غرار co-NP , P يمكن تعريف اقسام مشابهة وهي :

  •  \Delta_1=\mbox{P}
  •  \Delta_i=\mbox{P}^{\Delta_{i-1}}
  •  \Pi_1=\mbox{co-NP}
  •  \Pi_i=\mbox{co-NP}^{\Pi_{i-1}}

ويمكن تعريف PH بواسطة  \Delta_i او بواسطة \Pi_i وذلك لانَّ :

  •  \Pi_i \subseteq \Sigma_{i+1}
  •  \Sigma_i \subseteq \Pi_{i+1}
  •  \Sigma_i \cup \Pi_i \subseteq \Delta_i \subseteq \Sigma_{i+1} \cap \Pi_{i+1}

انهيار PH[عدل]

نقول أنَّ PH انهارت اذا تحقق التالي :

يوجد k بحيث أنَّ  \Sigma_k=\Sigma_{k+1}

حيث أنه اذا وجد k كهذا حينها :  \Sigma_k=\mbox{PH} واغلب علماء الحاسوب والرياضيات يقولون بعدم انهيار الهرم كثير الحدود , ومع هذا فإنه غير معلوم اذا ما PH مُنهار او لا !

علاقات مع اقسام اخرى[عدل]

  • يمكن بسهولة تبيين أنَّ  \mbox{PH}\subseteq \mbox{PSPACE} . وذلك لاننا يمكننا تجربة كل الامكانيات كما في تعريف PH ونستخدم مساحة اضافية متعددة الحدود .
  • اذا  \mbox{NP}=\mbox{coNP} حينها  \mbox{PH=NP}
  • لكل i اذا  \Sigma_i=\Pi_i حينها  \mbox{PH}=\Sigma_i
  • مبرهنة سبسر ولوتومان : \mbox{BPP}\subseteq \mbox{PH}
  • اذا  \mbox{NP} \subseteq \mbox{P/Poly} حينها :  \Sigma_2=\Pi_2 أي انه  \mbox{PH}=\Sigma_2 .
  • مبرهنة كانان : لكل k,  \Sigma_2 لا يتبع القسم : (Size(nk
  • مبرهنة تودا :  \mbox{PH}\subseteq  P^{\#P}

مسائل كاملة في Σi[عدل]

لكل Σi يمكن تعريف المسألة التالية : ΣiSAT :

المعطى : صيغة  \varphi(\mbox{x,y}) والتي هي بشكل SAT

المخرج : هل صحيح أنَّ :  \exists x \forall y_1 \exists y_2 \cdots Q_i y_i \varphi (\mbox{x},\mbox{y}_1,\cdots,\mbox{y}_i) حيث أنَّ :

 Q_i=\begin{cases} 
\forall,  & \mbox{if }i\mbox{ is even} \\
\exists, & \mbox{if }i\mbox{ is odd} 
\end{cases}

هذه المسألة كاملة ل- \Sigma_i . يمكن ايجاد مسائل اخرى كاملة [1] في الهامش .

مسائل كاملة في PH[عدل]

لنفرض أن المسألة L هي كاملة في PH , حينها يوجد k بحيث أنَّ  \mbox{L} \in \Sigma_k وبما أن هذه المسألة كاملة كل مسألة في PH يمكن اختزالها لهذه المسألة اي L ومن ضمن هذه المسائل نأخذ المسائل التي تتبع  \Sigma_{k+1} حينها كل مسألة كهذه تتبع أيضا  \Sigma_k وهذا يعني أنَّ  \Sigma_{k+1} \subseteq \Sigma_k وهذا يعني أنَّ  PH=\Sigma_k وهذا يعني أنَّ الهرم كثير الحدود ينهار ! لذا لا يمكن أن يكون هنالك مسائل كاملة الا اذا انهار PH . وهذا يعطي دليلا أنَّ PH و-PSPACE لا يمكن ان يكونا متساويتيين!

هامش[عدل]

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