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

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

## تعريف

* نعرف الاقسام التالية:
   * $\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$ يمكن تعريف المسألة التالية: Σ$_i$SAT :
المعطى: صيغة $\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 لا يمكن ان يكونا متساويتيين!

## هامش

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

## انظر أيضا

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