كثير حدود (تعقيد)
في علم التعقيد الحسابي الصنف P هو مجموعة كل المسائل التي يمكن تقريرها بواسطة آلة تيورنج قطعية بوقت بلونومي , لهذا الصنف من المسائل اهمية بالغة في علم الحاسوب والرياضيات إذ يُنظر اليها على انها مجموعة المسائل التي يمكن تطبيقها بشكل عملي معنى الكلام : هذه المجموعة من المسائل يمكن حلها بواسطة الحاسوب المعروف وذلك لان الات تيورنج عبارة عن محاكاة للحاسوب فهو النموذج الرياضي له وقد تحوي هذه المجموعة مسائل غير قابلة للتطبيق في الواقع لان كمية الخطوات بولونومي ولكن قد يفوق القدرة الحسابية للحاسوب مثلا :
مسالة وقت حلها formula_1 ، هذه المسالة غير عملية بالنسبة للحاسوب ولا يمكن تنفيذها ابدا ! حتى ولو كانت كمية المدخلات 2 !
يتجلى من هذا انه ليس كل ما كان بولونومي يكون حله عملي .
لهذا الصنف اهمية بالغة في علم الحاسوب والرياضيات التطبيقية ويرجع ذلك لكثرة ارتباطه بمسائل للوهلة الاولى لا تبدوا انها متعلقة بها ولكن في الحقيقة يوجد رابط غير مباشر .
مثل : البرهان الحسابي وكتابة البراهين العلمية والسؤال الذي حير العلماء لفترة طويلة هو هل يمكن كتابة او انتاج برهان بواسطة حاسوب ؟
وكما يتبين لك فان لهذا السؤال من الاهمية بمكان واذا ما تبيين اننا يمكن للحاسوب انتاج البراهين الرياضية العلمية فما نفع علماء الرياضيات ؟! واذا كان ذلك ممكنا فهل توجد طريقة لكتابة البرهان الأقصر ؟
هذا جانب واحد من ارتباط هذا الصنف بالرياضيات التطبيقية والعلاقة بينهما اوسع مما ذكرت بكثير .
جانب اخر لهذا الصنف وهو نظرية التعقيد الحسابي وهي ما محصلته تقول : هل هناك تعقيد حسابي ؟
بمعنى : هل لبنية المسالة علاقة بالوقت المطلوب لحلها ؟
هذا السؤال قد يبدو بسيطا ولكن في حقيقته معقد جدا وهو حدسية من الحدسيات التي يوليها العلم اهتماما بالغا وصيغة هذا الحدسية هي : NP=P ?
وعلى بساطتها فهي معقدة والرياضيات المطلوبة لاكتشاف الجواب قد لاتكون متوفرة بعد ما يجعلها من أكثر المسائل تعقيدا في زماننا .
ولهذا الصنف اهمية من جانب اخر وهو من جانب عالم الصناعات وتطوير الخوارزميات والاقتصاد وغيرها من المجالات المتعلقة .
أهم المسائل الموجودة في هذا الصنف من ضمنها :
هنالك الكثير من الحدسيات المرتبطة بهذا الصنف فمن ناحية يُعتبر النواة المؤسسة لكل علم التعقيد وهذه قائمة ببعض الحدسيات :
اغلب الظن أنَّ كل الاجوبة على هذه الاسئلة هو لا .
في حين أنَّ P هو صنف المتعلق بالة تيورنج قطعية متعددة الحدود الصنف NP متعلق بالة تيورنج غير القطعية , لذا فإن NP هي توسيع للصنف P . وبما أنَّ كل آلة تيورنج قطعية يمكن اعتبارها آلة تيورنج غير قطعية ولكن لا تستخدم التحزر لذا فإنَّ formula_10 الجهة العكسية هي حدسية لم تحل .
تطوير اخر ل-P هو الصنفبيسبايس إذ أنَّ بيسبايس هو الصنف الذي يحوي كل اللغات التي يمكن تقريرها بواسطة آلة تيورنج قطعية بحيث أنَّ سعة الموارد المستخدمة هو حدودي . من السهل التحقق من أنَّ : formula_11 وذلك لان كل آلة تيورنج عدد حسابتها حدودي في كل وقت يمكنها ان تستخدم على الأكثر سعة موارد حدودي , والجهة العكسية هي أيضا حدسية .
اذا سمحنا لالة تيورنج ان يكون وقتها أُسي حينها نحصل على الصنف EXPTIME ونلاحظ أنَّه وبشكل سهل انَّ formula_12 اما بالنسبة للجهة العكسية فقد تم حلها بواسطة مبرهنة هرمية الوقت(Time hierarchy theorem) , والنتيجة هي أنَّ formula_13 .
صنف اخر متعلق بالصنف P هو الصنف BPP وهو صنف لالات تيورنج الاحتمالية التي احتمال خطأها في التقرير بالنسبة لمُدخل هو اصغر من 1/3 . واغلب الظن ان الصنفين متساويين فمن جهة formula_14 ولكن من الجهة الاخرى غير معلومة .
توسيع اخر للصنفP هو الصنف P/Poly وهو صنف كل اللغات التي لها دائرة بوليانية حجمها متعدد الحدود لكل مدخل طوله n . من السهل التحقق من أنَّ formula_15 ولكن غير معلوم اذا ما formula_16 اذا لا فان هذا يعني أنَّ formula_17 .
ملاحظة : الصنف P/Poly يحتوي على لغات لا يمكن تقريرها بواسطة آلة تيورنج لذا فانه لا يمكن أن يكون مساويا ل-P او حتى NP او ل- EXP !
يمكن تلخيص كالتالي :