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

• فلتكن${\displaystyle L\subseteq \{0,1\}^{*}}$ مجموعة من الكلمات اي لغة نقول ان هذه اللغة موجودة في الصنف P إذا : هنالك بولينوم ${\displaystyle {\mbox{q(n)}}}$ بحيث أنَّ n هو طول المُدخل، وتوجد آلة تيورنج M بحيث ان عدد خطوات M الحسابية على كل مدخل ${\displaystyle x\in \{0,1\}^{*}}$ هو على الأكثر هو ${\displaystyle {\mbox{q(n)}}}$ . بالكتابة الرياضية :
• يمكن تعريف الصنف P على انه عائلة دوائر بوليانية موحدة .[1][2][3] اي ان لغة L تابعة للصنف P إذا يوجد عائلة دوائر بوليانية موحدة ${\displaystyle \{C_{n}:n\in \mathbb {N} \}}$ بحيث أنَّ لكل عدد المدخلات للدائرة البوليانية ${\displaystyle C_{n}}$ هو ${\displaystyle n}$ والمُخرج هو 1 بت وبالإضافة: ${\displaystyle \forall x\in \{0,1\}^{*}:x\in L\iff C_{|x|}(x)=1}$

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

• البرمجة الخطية
• حساب العامل المُشترك الأكبر لعددين
• ايجاد التلائم الاقصى في المخططات
• التحقق إذا ما عدد مُعطى هو أولي .
• ايجاد الشجرة الممتدة ذات الحد الادنى في المخططات (minimum spanning tree) .

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

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

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

complexity classes containments of each other

في حين أنَّ P هو صنف المتعلق بالة تيورنج قطعية متعددة الحدود الصنف NP متعلق بالة تيورنج غير القطعية، لذا فإن NP هي توسيع للصنف P . وبما أنَّ كل آلة تيورنج قطعية يمكن اعتبارها آلة تيورنج غير قطعية ولكن لا تستخدم التحزر لذا فإنَّ ${\displaystyle {\mbox{P}}\subseteq {\mbox{NP}}}$ الجهة العكسية هي حدسية لم تحل .

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

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

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

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

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

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

• ${\displaystyle {\mbox{L}}\subseteq {\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{PSPACE}}\subseteq {\mbox{EXP}}}$
• ${\displaystyle {\mbox{P}}\subseteq {\mbox{ZPP}}\subseteq {\mbox{RP}}\subseteq {\mbox{BPP}}\subseteq \Sigma _{2}^{P}\subseteq {\mbox{PSPACE}}\subseteq {\mbox{EXP}}}$
• ${\displaystyle {\mbox{P}}\subseteq {\mbox{ZPP}}\subseteq {\mbox{co-RP}}\subseteq {\mbox{BPP}}\subseteq \Sigma _{2}^{P}\subseteq {\mbox{PSPACE}}\subseteq {\mbox{EXP}}}$
• ${\displaystyle {\mbox{P}}\subset {\mbox{P/Poly}}}$

• نظرية التعقيد الحسابي.
• مسألة P=NP
• إن بي

• بوابة رياضيات
• بوابة علم الحاسوب