مسألة NP كاملة

من ويكيبيديا، الموسوعة الحرة

في الرياضيات صنف التعقيد، تعرف المسائل NP الكاملة، كل ما يحقق الشرطين الآتيين:

  1. كل مسألة من NP، تختصر لمسألة NP.
  2. المسألة NP.

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

فهرست

[تحرير] مبرهنة كوك و ليفين

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

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

[تحرير] مفهوم الإختصار

نقول أن A يتم اختصاره إلى B في وقت حدودي، في حالة وجود دالة قابلة للحساب في وقت حدودي، f : \left\{0,1\right\}^* \rightarrow \left\{0,1\right\}^* يحيث لكل x \in \left\{0,1\right\}^*, x \in L_1 إذا و فقط إذا كان f(x) \in L_2. نسمي الدالة f\! دالة الإختصار, و خوارزمية حدودية التي تحسب f\! يسمى خوارزمية الإختصار.

[تحرير] البرهنة

نقدم هنا برهنة تقريبية.

A مسألة من صنف NP. هذه المسألة مقبولة من آلة تورينغ M غير محددة. بالنسبة لكل مداخلة w ل M، توجد صيغة \varphi_w ذات بعد حدودي بالنسبة لبعد w و التي تكون كافية إذا و فقط إذا كانت w مقبولة من M.

نرمز ل n = | w | بعد w. بما أن الآلة M تعمل في وقت حدودي، يوجد عدد طبيعي ثابت k حيث كل عملية حسابية على w تكون على الأكثر بطول nk. نضيف سلسلة انتظار مغلقة، و نفترض أن طول العمليات هو بالضبط nk. آلة تورينغ تستعمل nk خلية. الإعدادات الخاصة بحساب مقبول يكون أيضا بطول nk. عند كتابة جميع الإعدادات الواحدة تحت الأخرى، تحصل على جدول. و نحصل على الصيغة \varphi_w التي ترمز لوجود جدول رموز محصل عن طريق الإعدادات المتتابعة لحساب مقبول ل w.

إعدادات 0 1 2 3 ... n^k فراغ
C0 = q0 W1 W2 W3 ... #
C1 = W'1 q1 W2 W3 ... #
C2 = W'1 W'2 q2 W3 ... #
C3 = ... ... ... ... ... #
... ... ... ... ... ... #
C_{n^k} ... ... ... ... ... ...

بالنسبة لكل خانة من الجدول و كل رمز a ، ندخل المتغير Xi,j,a الذي يرمز لكون الخانة تتضمن أو لا الرمز a. عدد هذه المتغيرات حدودي.

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

  • SATISFIABILITY : الإكتفاء، إيجاد قيم لمتغيرات ثنائية تجعل الصيغة العادية لعطف صحيحة.
  • CLIQUE : الزمرة، إيجاد زمرة أي مخطط كامل ذو بعد محدد ضمن مخطط آخر.
  • 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 :