كتب polynomial hierarchy
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
هرمية كثيرة الحدود (معلومة)
في نظرية التعقيد القسم PH هو قسم كل اللغات في هرم متعدد الحدود (Polynomial hierarchy) ، وهذا القسم يشمل جزء لا بأس به من الاقسام المعروفة مثل : NP ,co-NP ... وله عدة تعريفات متكافئة .
تعريف
- نعرف الاقسام التالية :
- وبطريقة البناء عن طريق الاستقراء نعرف :
- في حين أنَّ : هي مجموعة اللغات التي يمكن تقريرها بواسطة آلة تيورنج كثيرة الحدود غير قطعية مع امكانية الدخول إلى اوراكل من القسم C .
- حينها :
- 2. نعرف القسم بشكل اخر : إذا يوجد علاقة محدودة بكثير حدود وقابلة للتمييز بوقت كثير الحدود مع i+1 متغيرات حيث أنَّ : في حين أنَّ
يمكن ان نبين أنَّ التعريفان متكافئان وذلك بواسطة الاستقراء لكل i .
على غرار co-NP , P يمكن تعريف اقسام مشابهة وهي :
ويمكن تعريف PH بواسطة أو بواسطة وذلك لانَّ :
انهيار PH
نقول أنَّ PH انهارت إذا تحقق التالي :
يوجد k بحيث أنَّ
حيث أنه إذا وجد k كهذا حينها : واغلب علماء الحاسوب والرياضيات يقولون بعدم انهيار الهرم كثير الحدود، ومع هذا فإنه غير معلوم إذا ما PH مُنهار أو لا !
علاقات مع اقسام اخرى
- يمكن بسهولة تبيين أنَّ . وذلك لاننا يمكننا تجربة كل الامكانيات كما في تعريف PH ونستخدم مساحة اضافية متعددة الحدود .
- إذا حينها
- لكل i إذا حينها
- مبرهنة سبسر ولوتومان :
- إذا حينها : أي انه .
- مبرهنة كانان : لكل k، لا يتبع القسم : (Size(nk
- مبرهنة تودا :
مسائل كاملة في Σi
لكل Σi يمكن تعريف المسألة التالية : ΣiSAT :
المعطى : صيغة والتي هي بشكل SAT
المخرج : هل صحيح أنَّ : حيث أنَّ :
هذه المسألة كاملة ل- . يمكن ايجاد مسائل اخرى كاملة في الهامش .
مسائل كاملة في PH
لنفرض أن المسألة L هي كاملة في PH ، حينها يوجد k بحيث أنَّ وبما أن هذه المسألة كاملة كل مسألة في PH يمكن اختزالها لهذه المسألة اي L ومن ضمن هذه المسائل نأخذ المسائل التي تتبع حينها كل مسألة كهذه تتبع أيضا وهذا يعني أنَّ وهذا يعني أنَّ وهذا يعني أنَّ الهرم كثير الحدود ينهار ! لذا لا يمكن أن يكون هنالك مسائل كاملة الا إذا انهار PH . وهذا يعطي دليلا أنَّ PH و-PSPACE لا يمكن ان يكونا متساويتيين!
