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

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

تعريف

 
  1. نعرف الاقسام التالية:
  • Σ1=NP
  • وبطريقة البناء عن طريق الاستقراء نعرف: Σi=NPΣi1
في حين أنَّ:NPC هي مجموعة اللغات التي يمكن تقريرها بواسطة آلة تيورنج كثيرة الحدود غير قطعية مع امكانية الدخول إلى اوراكل من القسم C .
حينها: PH=i=0Σi
2. نعرف القسم Σi بشكل اخر:LΣi إذا يوجد علاقة محدودة بكثير حدود وقابلة للتمييز بوقت كثير الحدود مع i+1 متغيرات حيث أنَّ: xLy1y2Qiyi(x,y1,y2,,yi)RL في حين أنَّ

Qi={,i is even,i is odd

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

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

  • Δ1=P
  • Δi=PΔi1
  • Π1=co-NP
  • Πi=co-NPΠi1

ويمكن تعريف PH بواسطة Δi أو بواسطة Πi وذلك لانَّ:

  • ΠiΣi+1
  • ΣiΠi+1
  • ΣiΠiΔiΣi+1Πi+1

انهيار PH

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

يوجد k بحيث أنَّ Σk=Σk+1

حيث أنه إذا وجد k كهذا حينها: Σk=PH واغلب علماء الحاسوب والرياضيات يقولون بعدم انهيار الهرم كثير الحدود، ومع هذا فإنه غير معلوم إذا ما PH مُنهار أو لا !

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

  • يمكن بسهولة تبيين أنَّ PHPSPACE . وذلك لاننا يمكننا تجربة كل الامكانيات كما في تعريف PH ونستخدم مساحة اضافية متعددة الحدود.
  • إذا NP=coNP حينها PH=NP
  • لكل i إذا Σi=Πi حينها PH=Σi
  • مبرهنة سبسر ولوتومان: BPPPH
  • إذا NPP/Poly حينها: Σ2=Π2 أي انه PH=Σ2 .
  • مبرهنة كانان: لكل k، Σ2 لا يتبع القسم: (Size(nk
  • مبرهنة تودا: PHP#P

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

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

المعطى: صيغة φ(x,y) والتي هي بشكل SAT

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

xy1y2Qiyiφ(x,y1,,yi)

حيث أنَّ:

Qi={,i is even,i is odd

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

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

لنفرض أن المسألة L هي كاملة في PH ، حينها يوجد k بحيث أنَّ LΣk وبما أن هذه المسألة كاملة كل مسألة في PH يمكن اختزالها لهذه المسألة أي L ومن ضمن هذه المسائل نأخذ المسائل التي تتبع Σk+1 حينها كل مسألة كهذه تتبع أيضا Σk وهذا يعني أنَّ Σk+1Σk وهذا يعني أنَّ PH=Σk وهذا يعني أنَّ الهرم كثير الحدود ينهار ! لذا لا يمكن أن يكون هنالك مسائل كاملة الا إذا انهار PH . وهذا يعطي دليلا أنَّ PH و-PSPACE لا يمكن ان يكونا متساويتيين!

هامش

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

انظر أيضا