مسألة NP كاملة

مسألة NP كاملة
قابلية الإرضاء 3سات NAE OIT
تلوين مخطط تلوين مخطط بثلاثة ألوان تلوين مخطط مستو بثلاثة ألوان
زمرة كبرى
مسار هاملتونياني
عدل

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

• كل مسألة من صنف NP، تختصر لمسألة واحدة A.
• المسألة A من صنف NP.

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

مبرهنة كوك وليفين

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

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

مفهوم الاختصار

نقول أن $L_1$ يتم اختصاره إلى $L_2$ في وقت حدودي، في حالة وجود دالة قابلة للحساب في وقت حدودي، $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 تكون على الأكثر بطول $n^k$. نضيف سلسلة انتظار مغلقة، ونفترض أن طول العمليات هو بالضبط $n^k$. آلة تورينغ تستعمل $n^k$ خلية. الإعدادات الخاصة بحساب مقبول يكون أيضا بطول $n^k$. عند كتابة جميع الإعدادات الواحدة تحت الأخرى، تحصل على جدول. ونحصل على الصيغة $\varphi_w$ التي ترمز لوجود جدول رموز محصل عن طريق الإعدادات المتتابعة لحساب مقبول ل w.

إعدادات	0	1	2	3	...	n^k
$C_0 =$	$q_0$	$W_1$	$W_2$	$W_3$	...	#
$C_1 =$	$W'_1$	$q_1$	$W_2$	$W_3$	...	#
$C_2 =$	$W'_1$	$W'_2$	$q_2$	$W_3$	...	#
$C_3 =$	...	...	...	...	...	#
...	...	...	...	...	...	#
$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$

لائحة ب 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 :

أنظر أيضا

• نظرية التعقيد الحسابي.
• مسألة P=NP
• إن بي