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

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

تعريف

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_{i}y_{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(n^k
• مبرهنة تودا : ${\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}$ . يمكن ايجاد مسائل اخرى كاملة في الهامش .

مسائل كاملة في 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 لا يمكن ان يكونا متساويتيين!

انظر أيضا

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