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

• فلتكن${\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
• إن بي

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