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

من أرابيكا، الموسوعة الحرة

هذه هي النسخة الحالية من هذه الصفحة، وقام بتعديلها عبود السكاف (نقاش | مساهمات) في 21:51، 9 يوليو 2022 (بوت:تدقيق إملائي V2.2). العنوان الحالي (URL) هو وصلة دائمة لهذه النسخة.

(فرق) → نسخة أقدم | نسخة حالية (فرق) | نسخة أحدث ← (فرق)
اذهب إلى التنقل اذهب إلى البحث

في نظرية التعقيد القسم 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 على موقع واي باك مشين.

انظر أيضا