مرجع
آخر الزيارات

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

737 كلمة•0 مشاهدة•🗒️ منذ يوم
باختصار: في علم التعقيد الحسابي الصنف P هو مجموعة كل المسائل التي يمكن تقريرها بواسطة آلة تيورنج قطعية بوقت بلونومي، لهذا الصنف من المسائل اهمية بالغة في علم الحاسوب والرياضيات إذ يُنظر اليها على انها مجموعة المسائل التي يمكن تطبيقها بشكل عملي معنى…. تتناول المقالة 5 أقسام، منها «التعريف الرياضي»، «علاقة P مع اصناف أُخَر» و«حدسيات».
المحتويات
  1. التعريف الرياضي
  2. علاقة P مع اصناف أُخَر
  3. حدسيات
  4. مسائل مهمة موجودة في P
  5. ايجاد التلائم الاقصى في المخططات

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

إضافةً إلى ذلك، مسالة وقت حلها ، هذه المسالة غير عملية بالنسبة للحاسوب ولا يمكن تنفيذها أبدًا! حتى ولو كانت كمية المدخلات 2!

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

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

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

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

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

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

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

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

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

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

التعريف الرياضي

وفي هذا الصدد، يمكن تعريف الصنف P على انه عائلة دوائر بوليانية موحدة. أي ان لغة L تابعة للصنف P إذا يوجد عائلة دوائر بوليانية موحدة بحيث أنَّ لكل عدد المدخلات للدائرة البوليانية هو والمُخرج هو 1 بت وبالإضافة:

وفي هذا الصدد، فلتكن مجموعة من الكلمات أي لغة نقول ان هذه اللغة موجودة في الصنف P إذا: هنالك بولينوم بحيث أنَّ n هو طول المُدخل، وتوجد آلة تيورنج M بحيث ان عدد خطوات M الحسابية على كل مدخل هو على الأكثر هو . بالكتابة الرياضية:

علاقة P مع اصناف أُخَر

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

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

كذلك، توسيع اخر للصنفP هو الصنف P/Poly وهو صنف كل اللغات التي لها دائرة بوليانية حجمها متعدد الحدود لكل مدخل طوله n . من السهل التحقق من أنَّ ولكن غير معلوم إذا ما إذا لا فان هذا يعني أنَّ .

علاوةً على ذلك، إذا سمحنا لالة تيورنج ان يكون وقتها أُسي حينها نحصل على الصنف EXPTIME ونلاحظ أنَّه وبشكل سهل انَّ اما بالنسبة للجهة العكسية فقد تم حلها بواسطة مبرهنة هرمية الوقت(Time hierarchy theorem), والنتيجة هي أنَّ .

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

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

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

حدسيات

  • هل P=NP ?
  • هل P=PSPACE ?
  • هل P=BQP ?
  • هل P=BPP ?
  • هلL=P ?
  • هل PH=P ?
  • اغلب الظن أنَّ كل الاجوبة على هذه الاسئلة هو لا.

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

مسائل مهمة موجودة في P

  • أهم المسائل الموجودة في هذا الصنف من ضمنها:
  • البرمجة الخطية
  • حساب العامل المُشترك الأكبر لعددين

ايجاد التلائم الاقصى في المخططات

وفي السياق ذاته، ايجاد الشجرة الممتدة ذات الحد الادنى في المخططات (minimum spanning tree).

التحقق إذا ما عدد مُعطى هو أولي.

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.