مسألة NP كاملة
من ويكيبيديا، الموسوعة الحرة
في الرياضيات صنف التعقيد، تعرف المسائل NP الكاملة، كل ما يحقق الشرطين الآتيين:
- كل مسألة من NP، تختصر لمسألة NP.
- المسألة 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 = | ... | ... | ... | ... | ... | # | |
| ... | ... | ... | ... | ... | ... | # | |
|  | ... | ... | ... | ... | ... | ... | 
بالنسبة لكل خانة من الجدول و كل رمز 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 :

