مسألة NP كاملة |
---|
زمرة كبرى |
مسار هاملتونياني |
عدل |
في الرياضيات صنف التعقيد، تُعرف المسائل NP الكاملة، بأنها كل ما يحقق الشرطين الآتيين:
لتحديد وجودية المسائل NP الكاملة، قام كوك و كيفين باستعمال آلة تورينغ للبرهنة على وجود مسألة NP الكاملة، و هي صيغة قيم ثنائية مكونة من عطف عدة صيغ كل صيغة هي مجموعة فصل عدة متغيرات ثنائية أي لها 1 أو 0 كقيمة.
فهرس |
نص المبرهنة هو: SAT مشكل حدودي غير محدد كامل (NP-compet).
تنسب في الأغلب لكوك، حيث أن ليفين وجد نفس النتائج دون أن يكون على علم بنتائج كوك، ففي ذلك الوقت لم تكن هناك وسائل اتصال متطورة (ما بين 1971 و 1974).
نقول أن A يتم اختصاره إلى B في وقت حدودي، في حالة وجود دالة قابلة للحساب في وقت حدودي، يحيث لكل , إذا و فقط إذا كان . نسمي الدالة دالة الإختصار, و خوارزمية حدودية التي تحسب يسمى خوارزمية الإختصار.
نقدم هنا برهنة تقريبية.
A مسألة من صنف NP. هذه المسألة مقبولة من آلة تورينغ M غير محددة. بالنسبة لكل مداخلة w ل M، توجد صيغة ذات بعد حدودي بالنسبة لبعد w و التي تكون كافية إذا و فقط إذا كانت w مقبولة من M.
نرمز ل n = | w | بعد w. بما أن الآلة M تعمل في وقت حدودي، يوجد عدد طبيعي ثابت k حيث كل عملية حسابية على w تكون على الأكثر بطول nk. نضيف سلسلة انتظار مغلقة، و نفترض أن طول العمليات هو بالضبط nk. آلة تورينغ تستعمل nk خلية. الإعدادات الخاصة بحساب مقبول يكون أيضا بطول nk. عند كتابة جميع الإعدادات الواحدة تحت الأخرى، تحصل على جدول. و نحصل على الصيغة التي ترمز لوجود جدول رموز محصل عن طريق الإعدادات المتتابعة لحساب مقبول ل 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). و هي تضمن على الأقل أن متغير له القيمة 1 لكن متغيران و لكل لا يمكن أن يكون لهما القيمة 1 في نفس الوقت.
الصيغة تكتب على الشكل:
تكتب الصيغة هكذا:
مع ملاحظة أن D يرمز ل #.
هذه الصيغة تضمن على الأقل أن أحد خانات السطر الأخير من الجدول يضم حالة نهائية.
الصيغة تكتب على الشكل: