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

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

تعريف

1. نعرف الاقسام التالية:

• ${\displaystyle \Sigma _{1}={\mbox{NP}}}$
• وبطريقة البناء عن طريق الاستقراء نعرف: ${\displaystyle \Sigma _{i}={\mbox{NP}}^{\Sigma _{i-1}}}$

في حين أنَّ:${\displaystyle {\mbox{NP}}^{C}}$ هي مجموعة اللغات التي يمكن تقريرها بواسطة آلة تيورنج كثيرة الحدود غير قطعية مع امكانية الدخول إلى اوراكل من القسم C .

حينها: ${\displaystyle {\mbox{PH}}=\cup _{i=0}^{\infty }\Sigma _{i}}$

2. نعرف القسم ${\displaystyle \Sigma _{i}}$ بشكل اخر:${\displaystyle {\mbox{L}}\in \Sigma _{i}}$ إذا يوجد علاقة محدودة بكثير حدود وقابلة للتمييز بوقت كثير الحدود مع i+1 متغيرات حيث أنَّ: ${\displaystyle 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}}$ في حين أنَّ

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

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

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

• ${\displaystyle \Delta _{1}={\mbox{P}}}$
• ${\displaystyle \Delta _{i}={\mbox{P}}^{\Delta _{i-1}}}$
• ${\displaystyle \Pi _{1}={\mbox{co-NP}}}$
• ${\displaystyle \Pi _{i}={\mbox{co-NP}}^{\Pi _{i-1}}}$

ويمكن تعريف PH بواسطة ${\displaystyle \Delta _{i}}$ أو بواسطة ${\displaystyle \Pi _{i}}$ وذلك لانَّ:

• ${\displaystyle \Pi _{i}\subseteq \Sigma _{i+1}}$
• ${\displaystyle \Sigma _{i}\subseteq \Pi _{i+1}}$
• ${\displaystyle \Sigma _{i}\cup \Pi _{i}\subseteq \Delta _{i}\subseteq \Sigma _{i+1}\cap \Pi _{i+1}}$

انهيار PH

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

يوجد k بحيث أنَّ ${\displaystyle \Sigma _{k}=\Sigma _{k+1}}$

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

علاقات مع اقسام أخرى

• يمكن بسهولة تبيين أنَّ ${\displaystyle {\mbox{PH}}\subseteq {\mbox{PSPACE}}}$ . وذلك لاننا يمكننا تجربة كل الامكانيات كما في تعريف PH ونستخدم مساحة اضافية متعددة الحدود.
• إذا ${\displaystyle {\mbox{NP}}={\mbox{coNP}}}$ حينها ${\displaystyle {\mbox{PH=NP}}}$
• لكل i إذا ${\displaystyle \Sigma _{i}=\Pi _{i}}$ حينها ${\displaystyle {\mbox{PH}}=\Sigma _{i}}$
• مبرهنة سبسر ولوتومان: ${\displaystyle {\mbox{BPP}}\subseteq {\mbox{PH}}}$
• إذا ${\displaystyle {\mbox{NP}}\subseteq {\mbox{P/Poly}}}$ حينها: ${\displaystyle \Sigma _{2}=\Pi _{2}}$ أي انه ${\displaystyle {\mbox{PH}}=\Sigma _{2}}$ .
• مبرهنة كانان: لكل k، ${\displaystyle \Sigma _{2}}$ لا يتبع القسم: (Size(n^k
• مبرهنة تودا: ${\displaystyle {\mbox{PH}}\subseteq P^{\#P}}$

مسائل كاملة في Σ_i

لكل Σ_i يمكن تعريف المسألة التالية: Σ_iSAT :

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

المخرج: هل صحيح أنَّ: ${\displaystyle \exists x\forall y_{1}\exists y_{2}\cdots Q_{i}y_{i}\varphi ({\mbox{x}},{\mbox{y}}_{1},\cdots ,{\mbox{y}}_{i})}$ حيث أنَّ:

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

هذه المسألة كاملة ل-${\displaystyle \Sigma _{i}}$ . يمكن ايجاد مسائل أخرى كاملة ^[1] في الهامش.

مسائل كاملة في PH

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

هامش

1. phcom.dvi نسخة محفوظة 12 يوليو 2017 على موقع واي باك مشين.

انظر أيضا

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