مسألة NP كاملة

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

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

• لكل لغة,L, موجودة في NP يوجد دالة $f: \Sigma^* \rightarrow \Sigma^*$ بحيث ان عدد الحسابات التي تقوم بها هو دالة متعددة الحدود بالنسبة لمدخلها , بحيث ان f :

اذا $f(x) \in A\iff x \in L$ واذا $f(x) \notin A\iff x \notin L$

• المسألة A من صنف NP اي يمكن بناء آلة تورينغ غير حتمية تقرر اللغة A.

اول لغة عرفت بانها NP كاملة هي SAT حيث قام كل من كوك وليفين باثبات هذا كل على حدا, ومنذ ذلك الحين كثير من المسائل عُرف انها NP كاملة .

اللغة SAT

اولا نعرف ما هي الصيغ البوليانية : وهي معادلة فيها كل متغير يمكن ان يحصل على قيمتين 0 او 1 , وعادة ما يستخدم النفي( $\lnot$ ),العطف ( $\and$) او الفصل ($\or$)في الصيغة وتسمى هذه الصيغة CNF اذا كانت مركبة من عدة صيغ ثانوية بحيث ان كل صيغة كهذه هي فصل($\or$) عدة متغيرات والصيغة الاساسية هي عطف ( $\and$)الصيغ الثانوية .

واللغة SAT هي  : معطى صيغة CNF , $\phi$, هل يوجد قيم للمتغيرات بحيث ان الصيغة المعطاة قيمتها 1 ؟

مثال:لنفرض معطى : $\phi=(x_1 \or x_2)\and (\lnot x_1 \or x_2 \or x_3) \and (\lnot x_2)$ اذا عوضنا القيم التالية : $x_1=1,x_2=0,x_3=1$ الصيغة المعطاة تكون قيمها 1

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

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

تنسب في الأغلب لكوك، حيث أن ليفين وجد نفس النتائج دون أن يكون على علم بنتائج كوك، ففي ذلك الوقت لم تكن هناك وسائل اتصال متطورة (ما بين 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 : الزمرة، إيجاد زمرة أي مخطط(graph) كامل ذو بعد محدد ضمن مخطط آخر.
• 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 :

ماذا يعني NP كاملة؟

هذا بباسطة يعني انه اذا تمكن شخص من حل مسألة واحد NP-complete بوقت حدودي فهذا يعني انه يستطيع حل كل مسألة في NP , وقد تم برهنة التالي في حال حدوث امر مشابه :

• $EXP = NEXP$
• $PH=NP$
• لا يوجد دوال ذات اتجاه واحد (one way function)

من هذه النتائج نرى مدى اهمية هذه المسألة , ولكن للان لا احد يعرف اذا كان هناك حقا خوارزمية لحل مسالة NP كاملة بوقت حدودي .

أنظر أيضا

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