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

مسألة كثيرة حدود غير قطعية كاملة
في الرياضيات صنف التعقيد، تعرف المسائل كثيرة الحدود غير القطعية الكاملة، بأنها كل ما يحقق الشرطين الآتيين:
لكل لغة،L, موجودة في NP يوجد دالة بحيث ان عدد الحسابات التي تقوم بها هو دالة متعددة الحدود بالنسبة لمدخلها، بحيث ان f :
إذا وإذا
المسألة A من صنف NP أي يمكن بناء آلة تورنغ غير حتمية تقرر اللغة A.
أول لغة عرفت بانها NP كاملة هي SAT حيث قام كل من كوك وليفين باثبات هذا كل على حدا، ومنذ ذلك الحين كثير من المسائل عُرف انها NP كاملة.
أصول التسمية
في عام 1973 بادر دونالد كانوث في البحث عن مصطلح يصف أصعب المشاكل في NP. فقام باقتراع لدى الاختصاصيين. حصل على العديد من المقترحات البعض منها مبتكرة للغاية. وجاء الحل الفائز من مجموعة في مختبرات بل (ربما كان فيها ديفيد جونسون)، كما هو معروف: NP-صعب و NP-كامل.
يقول كانوث في النهاية: «المشاكل NP-صعبة تمس الكثير من الناس، وهذا هو السبب الذي جعلني أبحث عن مصطلح خاص يستخدم لدى الجميع. قول أن مشكل NP-صعب يقل تقنية لكنه ليس سيئ لغاية أن لا يكون صالحا للاستعمال.NP ، NP، P-صعب، أو NP-كامل، ما هي إلا عبارات جد تقنية تعزل الاختصاصيين وتدهش الآخرين.»
و يقدم جونسون توضيحات رفيعة المصداقية (صفحة 119 للكتاب وكذلك في المرجع) عن الدوافع الفعلية لكانوث وهي عندما بدأ تأليف المجلد الرابع لكتابه الذائع الصيت «فن برمجة الحاسوب» إبان ظهور نظرية التعقيد الحسابي غداة عمل ستيفن كوك ثم ريتشارد كارب ، لقد سئم من تكرار نفس الجملة الطويلة التي كانت تعرّف هذه الفئة من الخوارزميات قبل هذا. فأوقف كل شيء وأطلق دعوته لمصطلح مستحدث مرفقة بثلاثة اقتراحات رفضها الخبراء تلقائيا.
اللغة SAT
اولا نعرف ما هي الصيغ البوليانية: وهي معادلة فيها كل متغير يمكن ان يحصل على قيمتين 0 أو 1 , وعادة ما يستخدم النفي, العطف أو الفصلفي الصيغة وتسمى هذه الصيغة CNF إذا كانت مركبة من عدة صيغ ثانوية بحيث ان كل صيغة كهذه هي فصل عدة متغيرات والصيغة الاساسية هي عطفالصيغ الثانوية.
واللغة SAT هي: معطى صيغة CNF هل يوجد قيم للمتغيرات بحيث ان الصيغة المعطاة قيمتها 1 ؟
مثال: لنفرض معطى:
إذا عوضنا القيم التالية: الصيغة المعطاة تكون قيمها 1
مبرهنة كوك وليفين
نص المبرهنة هو: SAT مشكل حدودي غير محدد كامل (NP-complete).
تنسب في الأغلب لكوك، حيث أن ليفين وجد نفس النتائج دون أن يكون على علم بنتائج كوك، ففي ذلك الوقت لم تكن هناك وسائل اتصال متطورة (ما بين 1971 و 1974).
لائحة ب 21 مسألة NP كلاسيكية (كارب)
SATISFIABILITY : الاكتفاء، إيجاد قيم لمتغيرات ثنائية تجعل الصيغة العادية لعطف، صحيحة.
CLIQUE : الزمرة، إيجاد زمرة أي مخطط (graph) كامل ذو بعد محدد ضمن مخطط آخر.
SET PACKING :
VERTEX COVER : إيجاد ضمن مخطط مجموعة ارتباطات تتصل بكل القمم.
SET COVERING :
FEEDBACK ARC SET :
FEEDBACK NODE SET :
DIRECTED HAMILTONIAN CIRCUIT : البحث عن مسار هاملتونياني مغلق
UNDIRECTED HAMILTONIAN CIRCUIT : البحث عن مسار هاملتونياني مفتوح
0-1 INTEGER PROGRAMMING :
3-SAT : إيجاد قيم لمتغيرات ثنائية تجعل الصيغة العادية لعطف صحيحة تضم كل مجموعة 3 عناصر.
CHROMATIC NUMBER : تحديد أصغر عدد تلوين مخطط حيث كل قمتين مرتبطتين يكون لهما لونان مختلفان.
CLIQUE COVER :
EXACT COVER :
MATCHING à 3 dimensions :
STEINER TREE :
HITTING SET :
KNAPSACK :
JOB SEQUENCING :
PARTITION :
MAX-CUT :
المفهوم النظري المتوقع لحل مسألة كثيرة حدود غير قطعية كاملة
إذا تمكن شخص من حل مسألة واحد NP-complete بوقت حدودي فهذا يعني انه يستطيع حل كل مسألة في NP , وقد تم برهنة التالي في حال حدوث امر مشابه:
وهذا بشكل مباشر نابع من صفة الاختصار عند مسألة NP كاملة أي بما ان كل مسألة في NP يمكن اختصارها لهذه المسألة التي تتبع P حسب الفرضية أن المسائل الكاملة يمكن حلها بوقت حدودي حينها وبما ان الاختصار أيضا كثير حدود حينها نستطيع محاكاة الاختصار وايضا الآلة التي تحل المسألة الكاملة بوقت كثير الحدود لذا فانه كل مسألة في NP تتبع أيضا P .
وهذا نابع من علة التبطين. أي أن EXP صفاتها مشابهة لصفات P ولكن المقاييس يجب ان تكون أكبر.
وهذا يعتد به العلماء على ان حل مسائل NP كاملة غير ممكن، وذلك للاعتقاد ذي الدلائل ان PH وهو هرم مسائل كثيرة الحدود، انه لا يمكن ان ينهار لاي صنف ذي درجة نهائية.
لا يوجد دالة تشفير ذات اتجاه واحد (one way function) وهي دوال يسهل حسابها ولكن من الصعب حساب مقلوبها وهي تعتمد بشكل كبير على مسائل NP , ووجودها غير مؤكد حتى وان
هناك اثار أخرى منها ما يجعل العالم مكانا مثاليا والتطور التكنولوجي سوف يتضاعف خلال فترة هي قصيرة جدا، كما لحل هذه المسائل الكثير من التأثير في علم الحاسوب بكل فروعه والبيولوجيا والرياضيات.
حل مسائل كاملة كثيرة حدود غير قطعية هو مسألة مفتوحة وغير معلوم القدرة على حل مسائل كهذه أو عدمها، وقد عُرِض مليون دولار لمن يحل المسألة NP≠P والتي بعبارات أخرى هل يمكن حل مسائل NP كاملة بوقت حدودي؟ والذي يحل هذه المسألة يعني يأتي بخوارزمية تفعل هذا فانه يحصل ليس فقط على مليون ولكن ستة ملايين وذلك لانه يمكن حل المسائل الأخرى بواسطة هذه المسألة إذا كانت الإجابة أنَّ NP=P .
مراجع
انظر أيضا
نظرية التعقيد الحسابي.
مسألة P=NP
إن بي
أقسام التعقيد الحسابي
استمثال رياضي
علم الحاسوب في 1971
مسائل كثيرة حدود غير قطعية كاملة