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

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

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

في البداية، في الرياضيات صنف التعقيد، تعرف المسائل متعددة الحدود غير القطعية الكاملة ، بأنها كل ما يحقق الشرطين الآتيين:

من جانب آخر، لكل لغة،L, موجودة في NP يوجد دالة بحيث ان عدد الحسابات التي تقوم بها هو دالة متعددة الحدود بالنسبة لمدخلها، بحيث ان f :

إذا وإذا

ومن ناحية أخرى، المسألة A من صنف NP أي يمكن بناء آلة تورنغ غير حتمية تقرر اللغة A.

وعلى صعيد آخر، أول لغة عرفت بانها NP كاملة هي SAT حيث قام كل من كوك وليفين باثبات هذا كل على حدا، ومنذ ذلك الحين كثير من المسائل عُرف انها NP كاملة.

اللغة SAT

وعلى صعيد آخر، اولا نعرف ما هي الصيغ البوليانية: وهي معادلة فيها كل متغير يمكن ان يحصل على قيمتين 0 أو 1 , وعادة ما يستعمل النفي , العطف أو الفصل في الصيغة وتسمى هذه الصيغة CNF إذا كانت مركبة من عدة صيغ ثانوية بحيث ان كل صيغة كهذه هي فصل عدة متغيرات والصيغة الاساسية هي عطف الصيغ الثانوية.

إذا عوضنا القيم التالية: الصيغة المعطاة تكون قيمها 1

مثال: لنفرض معطى:

في هذا الإطار، واللغة SAT هي: معطى صيغة CNF , , هل يوجد قيم للمتغيرات بحيث ان الصيغة المعطاة قيمتها 1 ؟

مبرهنة كوك وليفين

من جهة ثانية، وهذا يعتد به العلماء على ان حل مسائل NP كاملة غير ممكن، وذلك للاعتقاد ذي الدلائل ان PH وهو هرم مسائل كثيرة الحدود، انه لا يمكن ان ينهار لاي صنف ذي درجة نهائية.

  • CLIQUE COVER :
  • EXACT COVER :
  • MATCHING à 3 dimensions :
  • STEINER TREE :
  • HITTING SET :
  • KNAPSACK :
  • JOB SEQUENCING :
  • PARTITION :
  • MAX-CUT :
  • المفهوم النظري المتوقع لحل مسألة كثيرة حدود غير قطعية كاملة

نص المبرهنة هو: SAT مشكل حدودي غير محدد كامل (NP-complete).

وفي السياق ذاته، لا يوجد دالة تشفير ذات اتجاه واحد (one way function) وهي دوال يسهل حسابها ولكن من الصعب حساب مقلوبها وهي تعتمد إلى حدّ كبير على مسائل NP , ووجودها غير مؤكد حتى وان

  • CLIQUE : الزمرة، إيجاد زمرة أي مخطط (graph) كامل ذو بعد محدد ضمن مخطط آخر.
  • SET PACKING :
  • VERTEX COVER : إيجاد ضمن مخطط مجموعة ارتباطات تتصل بكل القمم.
  • SET COVERING :
  • FEEDBACK ARC SET :
  • FEEDBACK NODE SET :
  • DIRECTED HAMILTONIAN CIRCUIT : البحث عن مسار هاملتونياني مغلق
  • UNDIRECTED HAMILTONIAN CIRCUIT : البحث عن مسار هاملتونياني مفتوح
  • 0-1 INTEGER PROGRAMMING :

وعلى صعيد آخر، CHROMATIC NUMBER : تحديد أصغر عدد تلوين مخطط حيث كل قمتين مرتبطتين يكون لهما لونان مختلفان.

وفي هذا الصدد، 3-SAT : إيجاد قيم لمتغيرات ثنائية تجعل الصيغة العادية لعطف صحيحة تضم كل مجموعة 3 عناصر.

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

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

مراجع

لائحة ب 21 مسألة NP كلاسيكية (كارب)

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

إضافةً إلى ذلك، وهذا نابع من علة التبطين. أي أن EXP صفاتها مشابهة لصفات P ولكن المقاييس يجب ان تكون أكبر.

إضافةً إلى ذلك، إذا تمكن شخص من حل مسألة واحد NP-complete بوقت حدودي فهذا يعني انه يستطيع حل كل مسألة في NP , وقد تم برهنة التالي في حال حدوث امر مشابه:

ومن جهة أخرى، حل مسائل كاملة كثيرة حدود غير قطعية هو مسألة مفتوحة وغير معلوم القدرة على حل مسائل كهذه أو عدمها، وقد عُرِض مليون دولار لمن يحل المسألة NP≠P والتي بعبارات أخرى هل يمكن حل مسائل NP كاملة بوقت حدودي؟ والذي يحل هذه المسألة يعني يأتي بخوارزمية تفعل هذا فانه يحصل ليس فقط على مليون ولكن ستة ملايين وذلك لانه يمكن حل المسائل الأخرى بواسطة هذه المسألة إذا كانت الإجابة أنَّ NP=P .

وفي هذا الصدد، SATISFIABILITY : الاكتفاء، إيجاد قيم لمتغيرات ثنائية تجعل الصيغة العادية لعطف، صحيحة.

أصول التسمية

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

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

وفي هذا الصدد، و يقدم جونسون توضيحات رفيعة المصداقية (صفحة 119 للكتاب وكذلك في المرجع) عن الدوافع الفعلية لكانوث وهي عندما بدأ تأليف المجلد الرابع لكتابه الذائع الصيت «فن برمجة الحاسوب» إبان ظهور نظرية التعقيد الحسابي غداة عمل ستيفن كوك ثم ريتشارد كارب ، لقد سئم من تكرار نفس الجملة الطويلة التي كانت تعرّف هذه الفئة من الخوارزميات قبل هذا. فأوقف كل شيء وأطلق دعوته لمصطلح مستحدث مرفقة بثلاثة اقتراحات رفضها الخبراء تلقائيا.

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

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

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