المحتوى هنا ينقصه الاستشهاد بمصادر، أي معلومات غير موثقة يمكن التشكيك بها وإزالتها.

كثير حدود (تعقيد)

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
Question book-new.svg
المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (مارس 2016)

في علم التعقيد الحسابي الصنف P هو مجموعة كل المسائل التي يمكن تقريرها بواسطة آلة تيورنج قطعية بوقت حدودي , لهذا الصنف من المسائل اهمية بالغة في علم الحاسوب والرياضيات إذ يُنظر اليها على انها مجموعة المسائل التي يمكن تطبيقها بشكل عملي , لقد كان تعريف هذا الصنف نقطة تحول في علم الحاسوب وكذلك كان لتعريف هذا الصنف علاقة مباشرة بتطوير علم التعقيد الحسابي وكذلك الحدسية الشهيرة : هل NP=P ? والتي ما زالت ضمن الحدسيات التي لا برهان لها ولها اثار عميقة في علم الحاسوب والرياضيات .

تعريف[عدل]

  • نقول أنَّ موجودة في الصنف اذا يوجد آلة تيورنج تقرر L , ويوجد متعدد الحدود بحيث أنَّ n هو طول المُدخل , بحيث أنَّ عدد حسابات M على المدخل هو على الأكثر هو .
  • يمكن تعريف الصنف P على انه عائلة دوائر بوليانية موحدة . اي ان لغة L تابعة للصنف P اذا يوجد عائلة دوائر بوليانية موحدة بحيث أنَّ لكل عدد المدخلات للدائرة البوليانية هو والمُخرج هو 1 بت وبالاضافة:

مسائل مهمة موجودة في P[عدل]

أهم المسائل الموجودة في هذا الصنف من ضمنها :

حدسيات[عدل]

هنالك الكثير من الحدسيات المرتبطة بهذا الصنف فمن ناحية يُعتبر النواة المؤسسة لكل علم التعقيد وهذه قائمة ببعض الحدسيات :

  • هل P=NP ?
  • هل P=PSPACE ?
  • هل P=BQP ?
  • هل P=BPP ?
  • هلL=P ?
  • هل PH=P ?

اغلب الظن أنَّ كل الاجوبة على هذه الاسئلة هو لا .

علاقة P مع اصناف أُخَر[عدل]

complexity classes containments of each other

في حين أنَّ P هو صنف المتعلق بالة تيورنج قطعية متعددة الحدود الصنف NP متعلق بالة تيورنج غير القطعية , لذا فإن NP هي توسيع للصنف P . وبما أنَّ كل آلة تيورنج قطعية يمكن اعتبارها آلة تيورنج غير قطعية ولكن لا تستخدم التحزر لذا فإنَّ الجهة العكسية هي حدسية لم تحل .

تطوير اخر ل-P هو الصنفبيسبايس إذ أنَّ بيسبايس هو الصنف الذي يحوي كل اللغات التي يمكن تقريرها بواسطة آلة تيورنج قطعية بحيث أنَّ سعة الموارد المستخدمة هو حدودي . من السهل التحقق من أنَّ : وذلك لان كل آلة تيورنج عدد حسابتها حدودي في كل وقت يمكنها ان تستخدم على الأكثر سعة موارد حدودي , والجهة العكسية هي أيضا حدسية .

اذا سمحنا لالة تيورنج ان يكون وقتها أُسي حينها نحصل على الصنف EXP ونلاحظ أنَّه وبشكل سهل انَّ اما بالنسبة للجهة العكسية فقد تم حلها بواسطة مبرهنة هرمية الوقت(Time hierarchy theorem) , والنتيجة هي أنَّ .

صنف اخر متعلق بالصنف P هو الصنف BPP وهو صنف لالات تيورنج الاحتمالية التي احتمال خطأها في التقرير بالنسبة لمُدخل هو اصغر من 1/3 . واغلب الظن ان الصنفين متساويين فمن جهة ولكن من الجهة الاخرى غير معلومة .

توسيع اخر للصنفP هو الصنف P/Poly وهو صنف كل اللغات التي لها دائرة بوليانية حجمها متعدد الحدود لكل مدخل طوله n . من السهل التحقق من أنَّ ولكن غير معلوم اذا ما اذا لا فان هذا يعني أنَّ .

ملاحظة : الصنف P/Poly يحتوي على لغات لا يمكن تقريرها بواسطة آلة تيورنج لذا فانه لا يمكن أن يكون مساويا ل-P او حتى NP او ل- EXP !

يمكن تلخيص كالتالي :

أنظر أيضا[عدل]