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

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

تعريف

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

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

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

حينها: $\text{PH}=\underset{i=0}{\overset{\mathrm{\infty }}{\cup }}{\mathrm{\Sigma }}_i$

2. نعرف القسم ${\mathrm{\Sigma }}_i$ بشكل اخر:$\text{L}\in {\mathrm{\Sigma }}_i$ إذا يوجد علاقة محدودة بكثير حدود وقابلة للتمييز بوقت كثير الحدود مع i+1 متغيرات حيث أنَّ: $x\in L⟺\mathrm{\exists }{y}_1\mathrm{\forall }{y}_2\cdots Q_i{y}_i(x,y_1,y_2,\cdots ,y_i)\in R_L$ في حين أنَّ

$Q_i=\{\begin{array}{cc}\mathrm{\forall },& i\text{ is even}\\ \mathrm{\exists },& i\text{ is odd}\end{array}$

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

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

• ${\mathrm{\Delta }}_1=\text{P}$
• ${\mathrm{\Delta }}_i={\text{P}}^{{\mathrm{\Delta }}_{i-1}}$
• ${\mathrm{\Pi }}_1=\text{co-NP}$
• ${\mathrm{\Pi }}_i={\text{co-NP}}^{{\mathrm{\Pi }}_{i-1}}$

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

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

انهيار PH

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

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

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

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

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

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

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

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

المخرج: هل صحيح أنَّ:

$\mathrm{\exists }x\mathrm{\forall }{y}_1\mathrm{\exists }{y}_2\cdots Q_i{y}_i\phi (\text{x},{\text{y}}_1,\cdots ,{\text{y}}_i)$

حيث أنَّ:

$Q_i=\{\begin{array}{cc}\mathrm{\forall },& i\text{ is even}\\ \mathrm{\exists },& i\text{ is odd}\end{array}$

هذه المسألة كاملة ل-${\mathrm{\Sigma }}_i$ . يمكن ايجاد مسائل أخرى كاملة في الهامش.

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

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

انظر أيضا

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