مسألة NP كاملة
من ويكيبيديا، الموسوعة الحرة
| مسألة NP كاملة | 
|---|
| 
 | 
| زمرة كبرى | 
| مسار هاملتونياني | 
| عدل | 
في الرياضيات صنف التعقيد، تُعرف المسائل NP الكاملة، بأنها كل ما يحقق الشرطين الآتيين:
- كل مسألة من صنف NP، تختصر لمسألة واحدة A.
- المسألة A من صنف NP.
لتحديد وجودية المسائل NP الكاملة، قام كوك و كيفين باستعمال آلة تورينغ للبرهنة على وجود مسألة NP الكاملة، و هي صيغة قيم ثنائية مكونة من عطف عدة صيغ كل صيغة هي مجموعة فصل عدة متغيرات ثنائية أي لها 1 أو 0 كقيمة.
| فهرست | 
[تحرير] مبرهنة كوك و ليفين
نص المبرهنة هو: SAT مشكل حدودي غير محدد كامل (NP-compet).
تنسب في الأغلب لكوك، حيث أن ليفين وجد نفس النتائج دون أن يكون على علم بنتائج كوك، ففي ذلك الوقت لم تكن هناك وسائل اتصال متطورة (ما بين 1971 و 1974).
[تحرير] مفهوم الإختصار
نقول أن A يتم اختصاره إلى B في وقت حدودي، في حالة وجود دالة قابلة للحساب في وقت حدودي،  يحيث لكل
 يحيث لكل  ,
,  إذا و فقط إذا كان
 إذا و فقط إذا كان  . نسمي الدالة
. نسمي الدالة  دالة الإختصار, و خوارزمية حدودية التي تحسب
 دالة الإختصار, و خوارزمية حدودية التي تحسب  يسمى خوارزمية الإختصار.
 يسمى خوارزمية الإختصار.
[تحرير] البرهنة
نقدم هنا برهنة تقريبية.
A مسألة من صنف NP. هذه المسألة مقبولة من آلة تورينغ M غير محددة. بالنسبة لكل مداخلة w ل M، توجد صيغة  ذات بعد حدودي بالنسبة لبعد w و التي تكون كافية إذا و فقط إذا كانت w مقبولة من M.
 ذات بعد حدودي بالنسبة لبعد w و التي تكون كافية إذا و فقط إذا كانت w مقبولة من M.
نرمز ل n = | w | بعد w. بما أن الآلة M تعمل في وقت حدودي، يوجد عدد طبيعي ثابت k حيث كل عملية حسابية على w تكون على الأكثر بطول nk. نضيف سلسلة انتظار مغلقة، و نفترض أن طول العمليات هو بالضبط nk. آلة تورينغ تستعمل nk خلية. الإعدادات الخاصة بحساب مقبول يكون أيضا بطول nk. عند كتابة جميع الإعدادات الواحدة تحت الأخرى، تحصل على جدول. و نحصل على الصيغة  التي ترمز لوجود جدول رموز محصل عن طريق الإعدادات المتتابعة لحساب مقبول ل 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 = | ... | ... | ... | ... | ... | # | |
| ... | ... | ... | ... | ... | ... | # | |
|  | ... | ... | ... | ... | ... | ... | 
بالنسبة لكل خانة  من الجدول مع
 من الجدول مع  و
 و  .و كل رمز
 .و كل رمز  ، ندخل المتغير
 ، ندخل المتغير  الذي يرمز لكون الخانة تتضمن أو لا الرمز
 الذي يرمز لكون الخانة تتضمن أو لا الرمز  . عدد هذه المتغيرات حدودي.
. عدد هذه المتغيرات حدودي.
عندنا العلاقة:  حيث كل من
 حيث كل من  و
 و  و
 و  و
 و  ترمز لوجود مسار مقبول.
 ترمز لوجود مسار مقبول.
[تحرير] الحصول على الصيغة 
الصيغة  هي صيغة عطف لكل خانة (i,j). و هي تضمن على الأقل أن متغير
 هي صيغة عطف لكل خانة (i,j). و هي تضمن على الأقل أن متغير  له القيمة 1 لكن متغيران
 له القيمة 1 لكن متغيران  و
 و  لكل
 لكل  لا يمكن أن يكون لهما القيمة 1 في نفس الوقت.
 لا يمكن أن يكون لهما القيمة 1 في نفس الوقت.
الصيغة تكتب على الشكل: ![\varphi_{cell} = \wedge_{0\le i,j\le n^k} \left[ (\vee_{a\in A} X_{i,j,a}) \wedge (\wedge_{a \ne b} \lnot(X_{i,j,a} \wedge X_{i,j,b}))  \right]](../../../math/7/6/4/764a26a82570beef0f60ee01d2198cd6.png)
[تحرير] الحصول على الصيغة 
تكتب الصيغة هكذا: 
مع ملاحظة أن D يرمز ل #.
[تحرير] الحصول على الصيغة 
هذه الصيغة تضمن على الأقل أن أحد خانات السطر الأخير من الجدول يضم حالة نهائية.
الصيغة تكتب على الشكل: 
[تحرير] الحصول على الصيغة 
[تحرير] لائحة ب 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 :

