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

في علم التعقيد الحسابي الصنف '''P''' هو مجموعة كل المسائل التي يمكن تقريرها بواسطة آلة تيورنج قطعية بوقت بلونومي، لهذا الصنف من المسائل اهمية بالغة في [[علم الحاسوب]] والرياضيات إذ يُنظر اليها على انها مجموعة المسائل التي يمكن تطبيقها بشكل عملي معنى الكلام: هذه المجموعة من المسائل يمكن حلها بواسطة الحاسوب المعروف وذلك لان الات تيورنج عبارة عن محاكاة للحاسوب فهو النموذج الرياضي له وقد تحوي هذه المجموعة مسائل غير قابلة للتطبيق في الواقع لان كمية الخطوات بولونومي ولكن قد يفوق القدرة الحسابية للحاسوب مثلا:

مسالة وقت حلها <math>n^{100}</math> ، هذه المسالة غير عملية بالنسبة للحاسوب ولا يمكن تنفيذها أبدًا! حتى ولو كانت كمية المدخلات 2!

يتجلى من هذا انه ليس كل ما كان بولونومي يكون حله عملي.

لهذا الصنف اهمية بالغة في علم الحاسوب و[[رياضيات|الرياضيات]] التطبيقية ويرجع ذلك لكثرة ارتباطه بمسائل للوهلة الأولى لا تبدوا انها متعلقة بها ولكن في الحقيقة يوجد رابط غير مباشر.

مثل: البرهان الحسابي وكتابة البراهين العلمية والسؤال الذي حير العلماء لفترة طويلة هو هل يمكن كتابة أو إنتاج برهان بواسطة حاسوب؟

وكما يتبين لك فان لهذا السؤال من الاهمية بمكان وإذا ما تبيين اننا يمكن للحاسوب إنتاج البراهين الرياضية العلمية فما نفع علماء الرياضيات؟! وإذا كان ذلك ممكنا فهل توجد طريقة لكتابة البرهان الأقصر؟

هذا جانب واحد من ارتباط هذا الصنف بالرياضيات التطبيقية والعلاقة بينهما اوسع مما ذكرت بكثير.

جانب اخر لهذا الصنف وهو نظرية التعقيد الحسابي وهي ما محصلته تقول: هل هناك تعقيد حسابي؟

بمعنى: هل لبنية المسالة علاقة بالوقت المطلوب لحلها؟

هذا السؤال قد يبدو بسيطا ولكن في حقيقته معقد جدا وهو حدسية من الحدسيات التي يوليها العلم اهتماما بالغا وصيغة هذا الحدسية هي: NP=P ?

وعلى بساطتها فهي معقدة والرياضيات المطلوبة لاكتشاف الجواب قد لاتكون متوفرة بعد ما يجعلها من أكثر المسائل تعقيدا في زماننا.

ولهذا الصنف اهمية من جانب اخر وهو من جانب عالم الصناعات وتطوير الخوارزميات والاقتصاد وغيرها من المجالات المتعلقة.

== التعريف الرياضي ==
* فلتكن<math> L \subseteq \{0,1\}^*</math> مجموعة من الكلمات أي لغة نقول ان هذه اللغة موجودة في الصنف P إذا: هنالك بولينوم <math>\mbox{q(n)}</math> بحيث أنَّ n هو طول المُدخل، وتوجد آلة تيورنج M بحيث ان عدد خطوات M الحسابية على كل مدخل <math> x \in \{0,1\}^* </math> هو على الأكثر هو <math>\mbox{q(n)}</math> . بالكتابة الرياضية:
*
*
*
* يمكن تعريف الصنف '''P''' على انه عائلة دوائر بوليانية موحدة.<ref>[https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf PRIMES is in P]", ''Annals of Mathematics'' 160 (2004), no. 2, pp. 781–793. {{Webarchive|url=https://web.archive.org/web/20171207171714/https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf |date=07 ديسمبر 2017}}</ref><ref>{{استشهاد بكتاب|الأخير=Hopcroft|الأول=John E.|عنوان=Introduction to automata theory, languages, and computation|مسار=https://archive.org/details/introductiontoau00jeho_379|سنة=2001|ناشر=Addison-Wesley|مكان=Boston|isbn=0201441241|صفحات=[https://archive.org/details/introductiontoau00jeho_379/page/n440 425]–426|إصدار=2.|مؤلف2=Rajeev Motwani |مؤلف3=Jeffrey D. Ullman }}</ref><ref>{{استشهاد بكتاب | الأخير = Immerman | الأول = Neil | وصلة مؤلف = Neil Immerman | عنوان = Descriptive Complexity | مسار = https://archive.org/details/descriptivecompl00imme_115 | سنة = 1999 | ناشر = Springer-Verlag | مكان = New York | isbn = 0-387-98600-6 | صفحة = [https://archive.org/details/descriptivecompl00imme_115/page/n77 66]}}</ref> أي ان لغة L تابعة للصنف '''P''' إذا يوجد عائلة دوائر بوليانية موحدة <math> \{C_n:n\in\mathbb{N}\}</math> بحيث أنَّ لكل عدد المدخلات للدائرة البوليانية <math>C_n</math> هو <math> n</math> والمُخرج هو 1 [[بت]] وبالإضافة: <math>\forall x \in \{0,1\}^* : x\in L \iff C_{|x|}(x)=1 </math>
== مسائل مهمة موجودة في P ==
أهم المسائل الموجودة في هذا الصنف من ضمنها:
* [[برمجة خطية|البرمجة الخطية]]
* حساب [[قاسم مشترك أكبر|العامل المُشترك الأكبر]] لعددين
* ايجاد [[تلائم(نظرية المخططات)|التلائم]] الاقصى في المخططات
* التحقق إذا ما عدد مُعطى هو [[عدد أولي|أولي]].
* ايجاد [[الشجرة الممتدة(نظرية المخططات)|الشجرة الممتدة]] ذات الحد الادنى في المخططات (minimum spanning tree).

== حدسيات ==
هنالك الكثير من الحدسيات المرتبطة بهذا الصنف فمن ناحية يُعتبر النواة المؤسسة لكل علم التعقيد وهذه قائمة ببعض الحدسيات:
* هل '''P'''='''NP''' ?
* هل '''P'''='''PSPACE''' ?
* هل '''P'''='''BQP''' ?
* هل '''P'''='''BPP''' ?
* هل'''L'''='''P''' ?
* هل '''PH'''='''P''' ?

اغلب الظن أنَّ كل الاجوبة على هذه الاسئلة هو لا.
== علاقة P مع اصناف أُخَر ==
[[ملف:ComplexityClassesRelations.jpg|تصغير|400px|complexity classes containments of each other]]
في حين أنَّ '''P''' هو صنف المتعلق بالة تيورنج قطعية [[متعددة الحدود]] الصنف '''NP''' متعلق بالة تيورنج غير القطعية، لذا فإن '''NP''' هي توسيع للصنف '''P''' . وبما أنَّ كل آلة تيورنج قطعية يمكن اعتبارها آلة تيورنج غير قطعية ولكن لا تستخدم التحزر لذا فإنَّ <math> \mbox{P} \subseteq \mbox{NP} </math> الجهة العكسية هي حدسية لم تحل.

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

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

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

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

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

يمكن تلخيص كالتالي:
* <math> \mbox{L} \subseteq \mbox{P} \subseteq \mbox{NP} \subseteq \mbox{PSPACE} \subseteq \mbox{EXP} </math>
* <math> \mbox{P} \subseteq \mbox{ZPP} \subseteq \mbox{RP} \subseteq \mbox{BPP} \subseteq \Sigma_2^P \subseteq \mbox{PSPACE} \subseteq \mbox{EXP} </math>
* <math> \mbox{P} \subseteq \mbox{ZPP} \subseteq \mbox{co-RP} \subseteq \mbox{BPP} \subseteq \Sigma_2^P \subseteq \mbox{PSPACE} \subseteq \mbox{EXP} </math>
* <math> \mbox{P} \subset \mbox{P/Poly} </math>

== انظر أيضا ==
* [[نظرية التعقيد الحسابي]].
* [[مسألة كثير حدود وكثير حدود غير قطعي|مسألة P=NP]]
* [[كثير حدود غير قطعي|إن بي]]
== مراجع ==
{{مراجع}}

{{أقسام تعقيد}}
{{شريط بوابات|رياضيات|علم الحاسوب}}

[[تصنيف:أقسام التعقيد الحسابي]]
[[تصنيف:استمثال رياضي]]