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

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

انظر أيضا



  • بوابة رياضيات
  • بوابة علم الحاسوب
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.