انتقل إلى المحتوى

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

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

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

تعريف

[عدل]
  1. نعرف الاقسام التالية:
  • وبطريقة البناء عن طريق الاستقراء نعرف:
في حين أنَّ: هي مجموعة اللغات التي يمكن تقريرها بواسطة آلة تيورنج كثيرة الحدود غير قطعية مع امكانية الدخول إلى اوراكل من القسم C .
حينها:
2. نعرف القسم بشكل اخر: إذا يوجد علاقة محدودة بكثير حدود وقابلة للتمييز بوقت كثير الحدود مع i+1 متغيرات حيث أنَّ: في حين أنَّ

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

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

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

انهيار PH

[عدل]

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

يوجد k بحيث أنَّ

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

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

[عدل]
  • يمكن بسهولة تبيين أنَّ . وذلك لاننا يمكننا تجربة كل الامكانيات كما في تعريف PH ونستخدم مساحة اضافية متعددة الحدود.
  • إذا حينها
  • لكل i إذا حينها
  • مبرهنة سبسر ولوتومان:
  • إذا حينها: أي انه .
  • مبرهنة كانان: لكل k، لا يتبع القسم: (Size(nk
  • مبرهنة تودا:

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

[عدل]

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

المعطى: صيغة والتي هي بشكل SAT

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

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

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

[عدل]

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

هامش

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

انظر أيضا

[عدل]