مسألة NP كاملة

مسألة NP كاملة
	قابلية الإرضاء 3SAT; 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\geq i$ و $j\leq 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\neq b\,$ لا يمكن أن يكون لهما القيمة 1 في نفس الوقت.

الصيغة تكتب على الشكل: $\varphi _{cell}=\wedge _{0\leq i,j\leq n^{k}}\left[(\vee _{a\in A}X_{i,j,a})\wedge (\wedge _{a\neq 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\leq j\leq n^{k}}\;and\;{q\in F}\;^{x}\!n^{k},j,q$

الحصول على الصيغة $\varphi _{move}$

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