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

مسألة كثير حدود وكثير حدود غير قطعي

1٬304 كلمة•0 مشاهدة•🗒️ منذ 17 يوماً
باختصار: إن العلاقة بين مسائل التعقيد كثيرة الحدود وكثير حدود غير قطعي هي مسألة غير محلولة في المعلوماتية النظرية. تتناول المقالة 3 أقسام، منها «كاملة»، «صيغة المسألة» و«توابع جواب الحدسية».
المحتويات
  1. كاملة
  2. صيغة المسألة
  3. توابع جواب الحدسية
مسألة كثير حدود وكثير حدود غير قطعي

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

وفي هذا السياق، خذ مثلًا مسألة مجموع المجموعات الجزئية، وهو مثال على مسألة من السهل التحقق من صحة جوابها، لكن عملية حساب الجواب نفسه يعتبر (هذا الأمر غير مبرهن بعد) من الأمور الصعبة. مثلًا هل يوجد مجموعة جزئية من المجموعة التالية {2−, 3−, 15, 14, 7, 10−} يكون مجموع عناصرها مساويا للصفر؟ الجواب بكل بساطة هو نعم، لأن المجموعة الجزئية {2−, 3−,10−, 15} مجموعها صفر وهو أمر من الممكن التحقق منه بكل بساطة بجمع العناصر. لكن إن عملية إيجاد كل مجموعة جزئية من المجموعة الأساسية يكون مجموع جميع عناصرها ينتهي إلى الصفر يأخذ وقتا طويلا.

من جانب آخر، جوهر المسألة في أنه إذا كان من الممكن التأكد من الجواب الصحيح لمسألة ما بعد الحصول عليه في الزمن الخطي فهل من الممكن كذلك حساب هذه الأجوبة ذاتها بسرعة؟

كاملة

ومن جهة أخرى، اما الصفة الثانية فهي تحتاج إلى تعريف الاختصار والذي هو : فلتكن A , B مسألتان اختصار المسألة A للمسألة B هو دالة f حيث انها تحقق التالي : . أي ان الدالة f تحول مُدخلات المسألة A إلى مُدخل ملائم للدالة B . الاختصار كما عرفناه لا ينفع لانه لا يحقق النجاعة الكافية حيث ان الدالة f يمكن ان تكون غير قابلة للحساب، ولكن نحدد الدالة f لتكون قابلة للحساب بل ويمكن حسابها بوقت كثير الحدود .

وفي السياق ذاته، اما الصفة الأولى فقد نبعت من كون مجال بحث المسألة «كبير جدا» وكذلك لان لا أحد نجح بالإتيان بخوارزمية لحلها، مثلا مسألة الاكتفاء : معطى صيغة بوليانية ونريد ان نعرف هل قابلة للاكتفاء، الطريقة الوحيدة هي كتابة كل التعويضات الممكنة للمتغيرات وفحصها هل تكفي الصيغة ام لا، هذه الخوارزمية من أفضل الخوارزميات لهذه المسألة للان ولكن هذه الخوارزمية تعبر على كل مجال البحث وهذا يعني انها ستعبر على , هذه الدالة الأُسية عندما يكون n=80 حينها لو انك عشت من أول خلق الكون ليومنا ما انتهت من البحث !

ومن ناحية أخرى، من خلال البحث عن اسلوب أو طريقة لحل المسألة ظهرت أنواع مسائل من نوع اخر، وهذه المسائل كان لها صفتين :

في هذا الإطار، مصطلح الاختصار فتح باباً لتكون لتعريف متى المسائل مطابقة (مع فارق وقت حدودي) , لذا فاننا نعرف المسائل NP كاملة لتكون كل المسائل التي تتبع NP ويمكن اختصار كل المسائل في NP لهذه المسألة، من الوهلة الأولى لا يبدو ان هذه المسائل موجودة وذلك لقوتها الهائلة وذلك لان حلها يعني ان تكون قادرا على حل كثير من المسائل، ولكن المفاجأة انه يوجد مسائل كهذه وهي شائعة وكثيرة ولها كثير من التطبيقات العملية تنبسط على كل مجالات علم الحاسوب على وجه التقريب، ولكن هل يمكن ان نحل هذه المسائل بنجاعة ؟ لا نعرف، وذلك لان هذا السؤال مساوي ومكافئ للسؤال هل NP=P . وبالتحديد يمكن حلها بنجاعة فقط إذا P=NP .

يمكن تحويل هذه المسائل ما بين بعضها بسرعة .

وفي هذا السياق، بعض الأمثلة لهذه المسائل من ضمنها مسألة الاكتفاء، هل يوجد في مخطط معطى مسار هاميلتوني ؟ وكثير من الاسئلة واسعة الاستخدام .

لا يوجد لها خوارزمية ناجحة تحلها .

صيغة المسألة

ومن جهة أخرى، لنفترض أن المجموعة الأولى هي {1,2,3,4}وفيها الرقم 2 كمحتوى على متنها ولكن احتواء المجموعة الثانية للرقم 2 ليس احتواء شاملا سوى للرقمين 1,2 و بالتالي :NP ليست تساوي P .

علاوةً على ذلك، المسألة الصعبة والتي لا برهان لها هي الاحتواء الثاني (أي احتواء NP على P ) لذا فان المسألة هي هل NP تحوي المجموعة P أم أن الأمر غير ذلك ؟

وفي السياق ذاته، المسالة P = NP هي تحديد إذا ما كل مسألة يمكن تقريرها بواسطة خوارزمية غير قطعية يمكن كذلك حلها بواسطة خوارزمية قطعية . حتى نستطيع تعريف المسألة بشكل دقيق يجب علينا تحديد نموذج حاسوبي . النموذج الأساسي للحاسوب في النظرية الحاسوبية هي آلة تورنغ والتي عرفها آلان تورنغ عام 1936 و بالرغم من أن هذا النموذج ظهر قبل الحاسوب الذي نعرفه الٱن لكنه أنموذج مقبول نظر لأساسيته الهادفة والثابتة الهدف أجلا وأملا في تعريف المصطلح كدالة قابلة للحساب .

وفي هذا السياق، لقد افترضت كل المناقشات السابقة أن P تعني "سهل" وأن "ليس في P يعني "صعب"، وهو افتراض يُعرف باسم فرضية كوبام. يعد هذا الافتراض شائعاً في نظرية التعقيد، ولكن هناك بعض التحفظات عليه.

وفي هذا الصدد، تقديم آلة تورنج كان أحد أهم الخطوات في جعل الحاسوب نموذجا رياضيا والأهم من هذا باتت قدرتنا ٱنيا تتيح لنا إعطاء تعريف دقيق للقسم أو الصنف P بالإضافة للصنف المضاد NP , ولكن تنقص بعض التعريفات المهمة منها تعريف لغة آلة تورنج بشكل غير رسمي هي كل المُداخلات التي تنمذجها آلة تورنج والتي دورها تقديم صواب الجواب ب «نعم» و بشكل دقيق ونعرفها كالٱتي : فلتكن M آلة تورنج، ولنفترض أنَّ هي أبجدية الآلة (ٱلة تورنغ) حينها نعرف لغة الآلة أنها كالتالي: .

إضافةً إلى ذلك، من التعريفين السابقين صيغة المسألة بشكل دقيق ستكون كالتالي : نعرف P لتكون , ونعرف NP ليكون , والسؤال هو هل هاتين المجموعتين متساويتين ؟

هل P تعني "سهل"؟

ومن جهة أخرى، نجاعة الخوارزمية في هذه الحالة هي كمية الوقت التي تستعملها الخوارزمية حتى الوصول للنتيجة الدقيقة : فلتكن دالة من الأعداد الطبيعية إلى الأعداد الطبيعية (نسميها في كثير من الأحيان دالة وقتية أو دالة الوقت) حينها نرمز ل- هي مجموعة كل المسائل التي توجد آلة تورنج على متنها محتمة وتحلها خلال و عدد خطوات الحساب التي تلزم الآلة للوصول لصواب الجواب حيث نستطيع كذلك وبشكل مشابه تعريف لكن الأنموذج يبرز ٱلة تورنج غير الحتمية .

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

ومن ناحية أخرى، أخيراً، هناك أنواع من العمليات الحسابية لا تتوافق مع نموذج آلة تورينج الذي تُعرف P وNP عليه، مثل الحوسبة الكمومية والخوارزميات العشوائية.

من جانب آخر، ثانياً، حتى إذا تبين أن مشكلة ما من فئة مسألة كثيرة حدود، وحتى لو كانت P ≠ NP، قد تظل هناك طرق فعالة للمشكلة من الناحية العملية. توجد خوارزميات للعديد من مشكلات مسألة كثيرة حدود، مثل مسألة حقيبة الظهر، ومسألة البائع المتجول، ومسألة الاستيفاء منطقية، والتي يمكن أن تحل بشكل مثالي الكثير من الحالات الواقعية في وقت معقول. قد يكون متوسط التعقيد التجريبي للحالة (الوقت مقابل حجم المشكلة) لمثل هذه الخوارزميات منخفضًا بشكل مدهش. ومن الأمثلة على ذلك طريقة التبسيط في البرمجة الخطية، والتي تعمل بشكل جيد بشكل مدهش في الممارسة العملية؛ على الرغم من أن لديها تعقيدًا زمنيًا أسيًا في أسوأ الحالات، إلا أنها تعمل على قدم المساواة مع أفضل الخوارزميات المعروفة في الزمن متعدد الحدود.

وفي هذا السياق، أولاً، قد تحتوي الخوارزمية النظرية متعددة الحدود على عوامل ثابتة أو أسس كبيرة للغاية، مما يجعلها غير عملية. مثلًا، يمكن حل مشكلة تحديد ما إذا كانت الرسم البياني يحتوي على H كـ "ماينور"، حيث H ثابت، في زمن تشغيل يبلغ O(n2)، حيث n هو عدد الرؤوس في G. ومع ذلك، فإن تمثيل O الكبير (تمثيل O الكبرى) يخفي ثابتًا يعتمد بشكل فوق أسي على H. هذا الثابت أكبر من (باستخدام ترميز سهم لأعلى لكينوث)، حيث h هو عدد الرؤوس في H.

توابع جواب الحدسية

هناك حالتين :

  • مراجع
  • انظر كذلك
  • كثيرة حدود غير قطعية
  • غريغوري تشايتين
  • كثيرة حدود غير قطعية كاملة

وفي السياق ذاته، اما إذا NP≠P فهي أكثر منطقية من توابع الأولى إذ انه ما كنا نعتقد انه صعب فهو حتما كذلك وكل ما تطور من نظريات ووسائل في الثلاثين عاما الاخيرة كانت مفيدة جدا في تقدم العالم .

وفي هذا الصدد، NP=P , وهذا سيغير الحياة التي سنعرفها إلى الابد فلهذا توابع جميلة تصل إلى درجة الخيال، وذلك لانه بعد ان تبين (فرضا) أن NP=P , حينها الحياة أسهل ومثالية إذ انه لسنا بحاجة إلى رياضيين ليبرهنوا الحدسيات بل يمكننا ان نشغل برنامج الذي يحاكي عمل الرياضي، كما ان تصميمات الذكاء الاصطناعي ستكون دقيقة ولسنا بحاجة إلى أي نوع من التقريب كما ان العشوائية لن تكون ذي نفع يذكر ! وكثير من الامور التي هي ضرب من الخيال المحض ولكن لا أحد نجح في تفنيد NP=P وقد ظلت هذه المسالة جاثمة دون برهان أو تفنيد لاكثر من 30 عام .

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

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

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