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

من ويكيبيديا، الموسوعة الحرة
(بالتحويل من مسألة NP كاملة)
اذهب إلى: تصفح، ‏ ابحث
مسألة NP كاملة
زمرة كبرى
مسار هاملتونياني
عدل

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

  • لكل لغة,L, موجودة في NP يوجد دالة f: \Sigma^* \rightarrow \Sigma^* بحيث ان عدد الحسابات التي تقوم بها هو دالة متعددة الحدود بالنسبة لمدخلها , بحيث ان f :

اذا  f(x) \in A\iff x \in L واذا  f(x) \notin A\iff x \notin L

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

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

اللغة SAT[عدل]

اولا نعرف ما هي الصيغ البوليانية : وهي معادلة فيها كل متغير يمكن ان يحصل على قيمتين 0 او 1 , وعادة ما يستخدم النفي( \lnot ),العطف (  \and ) او الفصل ( \or )في الصيغة وتسمى هذه الصيغة CNF اذا كانت مركبة من عدة صيغ ثانوية بحيث ان كل صيغة كهذه هي فصل( \or ) عدة متغيرات والصيغة الاساسية هي عطف (  \and )الصيغ الثانوية .

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

مثال:لنفرض معطى : \phi=(x_1 \or x_2)\and (\lnot x_1 \or x_2 \or x_3) \and (\lnot x_2) اذا عوضنا القيم التالية : x_1=1,x_2=0,x_3=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 , وقد تم برهنة التالي في حال حدوث امر مشابه :

  • \mbox{ NP=P} وهذا بشكل مباشر نابع من صفة الاختصار عند مسألة NP كاملة اي بما ان كل مسألة في NP يمكن اختصارها لهذه المسألة التي تتبع P حسب الفرضية أن المسائل الكاملة يمكن حلها بوقت حدودي حينها وبما ان الاختصار ايضا كثير حدود حينها نستطيع محاكاة الاختصار وايضا الالة التي تحل المسألة الكاملة بوقت كثير الحدود لذا فانه كل مسألة في NP تتبع ايضا P .
  •  \mbox{EXP = NEXP} وهذا نابع من علة التبطين . اي أن EXP صفاتها مشابهة لصفات P ولكن المقاييس يجب ان تكون اكبر .
  •   \mbox{PH=NP} وهذا يعتد به العلماء على ان حل مسائل NP كاملة غير ممكن , وذلك للاعتقاد ذي الدلائل ان PH وهو هرم مسائل كثيرة الحدود , انه لا يمكن ان ينهار لاي صنف ذي درجة نهائية .
  • لا يوجد دالة تشفير ذات اتجاه واحد (one way function) وهي دوال يسهل حسابها ولكن من الصعب حساب مقلوبها وهي تعتمد بشكل كبير على مسائل NP , ووجودها غير مؤكد حتى وان  NP \neq P

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

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

أنظر أيضا[عدل]