الرئيسيةبحث

مسألة NP كاملة

مسألة NP كاملة
زمرة كبرى
مسار هاملتونياني
عدل

في الرياضيات صنف التعقيد، تُعرف المسائل 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} ... ... ... ... ... ...

بالنسبة لكل خانة (i,j) \, من الجدول مع 0 \ge i و j \le n^k .و كل رمز a \, ، ندخل المتغير X_{i,j,a} \, الذي يرمز لكون الخانة تتضمن أو لا الرمز a \,. عدد هذه المتغيرات حدودي.

عندنا العلاقة: \varphi_w = \varphi_{cell} \wedge \varphi_{start} \wedge \varphi_{move} \wedge \varphi_{accept} حيث كل من \varphi_{cell} و \varphi_{start} و \varphi_{move} و \varphi_{accept} ترمز لوجود مسار مقبول.

الحصول على الصيغة \varphi_{cell}

الصيغة \varphi_{cell} \, هي صيغة عطف لكل خانة (i,j). و هي تضمن على الأقل أن متغير X_{i,j,a} \, له القيمة 1 لكن متغيران X_{i,j,a} \, و X_{i,j,b} \, لكل a \ne b \, لا يمكن أن يكون لهما القيمة 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]

الحصول على الصيغة \varphi_{start}

تكتب الصيغة هكذا: x_{0,0,q_0}\wedge x_{0,1,w_1}\wedge x_{0,2,w_2}\wedge ...\wedge x_{0,n,w_n}\wedge x_{0,n+1,D}\wedge ...\wedge x_{0,n^k,D}

مع ملاحظة أن D يرمز ل #.

الحصول على الصيغة \varphi_{accept}

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

الصيغة تكتب على الشكل: \varphi_{accept} = \lor_{0\le j\le n^k} \;and\; {q\in F}\; ^x\!n^k,j,q

الحصول على الصيغة \varphi_{move}

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

المسائل الكلاسيكية
المسائل الكلاسيكية

أنظر أيضا