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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

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

تعريف[عدل]

  • نقول أنَّ  L \subseteq \{0,1\}^* موجودة في الصنف \mbox{P} اذا يوجد آلة تيورنج \mbox{M} تقرر L , ويوجد متعدد الحدود \mbox{q(n)} بحيث أنَّ n هو طول المُدخل , بحيث أنَّ عدد حسابات M على المدخل  x \in \{0,1\}^* هو على الأكثر هو \mbox{q(n)} .
  • يمكن تعريف الصنف P على انه عائلة دوائر بوليانية موحدة . اي ان لغة L تابعة للصنف P اذا يوجد عائلة دوائر بوليانية موحدة  \{C_n:n\in\mathbb{N}\} بحيث أنَّ لكل عدد المدخلات للدائرة البوليانية C_n هو  n والمُخرج هو 1 بت وبالاضافة: \forall x \in \{0,1\}^* : x\in L \iff C_{|x|}(x)=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 . وبما أنَّ كل آلة تيورنج قطعية يمكن اعتبارها آلة تيورنج غير قطعية ولكن لا تستخدم التحزر لذا فإنَّ  \mbox{P} \subseteq \mbox{NP} الجهة العكسية هي حدسية لم تحل .

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

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

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

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

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

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

  •  \mbox{L} \subseteq \mbox{P} \subseteq \mbox{NP} \subseteq \mbox{PSPACE} \subseteq \mbox{EXP}
  •  \mbox{P} \subseteq \mbox{ZPP} \subseteq \mbox{RP} \subseteq \mbox{BPP} \subseteq \Sigma_2^P \subseteq \mbox{PSPACE} \subseteq \mbox{EXP}
  •  \mbox{P} \subseteq \mbox{ZPP} \subseteq \mbox{co-RP} \subseteq \mbox{BPP} \subseteq \Sigma_2^P \subseteq \mbox{PSPACE} \subseteq \mbox{EXP}
  •  \mbox{P} \subset \mbox{P/Poly}

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