مسألة NP كاملة

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

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

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

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

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

نص المبرهنة هو: SAT مأزق حدودي غير محدد تام (NP-compet).

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

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

نقول حتى ${\displaystyle L_{1$ يتم اختصاره إلى ${\displaystyle L_{2$ في وقت حدودي، في حالة وجود دالة قابلة للحساب في وقت حدودي، ${\displaystyle f:\left\{0,1\right\ ^{* \rightarrow \left\{0,1\right\ ^{*$ يحيث لكل ${\displaystyle x\in \left\{0,1\right\ ^{*$ , ${\displaystyle x\in L_{1$ إذا وفقط إذا كان ${\displaystyle f(x)\in L_{2$ . نسمي الدالة ${\displaystyle f\!$ دالة الإختصار, وخوارزمية حدودية التي تحسب ${\displaystyle f\!$ يسمى خوارزمية الإختصار.

البرهنة

نقدم هنا برهنة تقريبية.

A مسألة من صنف NP. هذه المسألة مقبولة من آلة تورينغ M غير محددة. بالنسبة لكل مداخلة w ل M، توجد صيغة ${\displaystyle \varphi _{w$ ذات بعد حدودي بالنسبة لبعد w والتي تكون كافية إذا وفقط إذا كانت w مقبولة من M.

نرمز ل ${\displaystyle n=|w|$ بعد w. بما حتى الآلة M تعمل في وقت حدودي، يوجد عدد طبيعي ثابت k حيث جميع عملية حسابية على w تكون على الأكثر بطول ${\displaystyle n^{k$ . نضيف سلسلة انتظار مغلقة، ونفترض حتى طول العمليات هوبالضبط ${\displaystyle n^{k$ . آلة تورينغ تستعمل ${\displaystyle n^{k$ خلية. الإعدادات الخاصة بحساب مقبولقد يكون أيضا بطول ${\displaystyle n^{k$ . عند كتابة جميع الإعدادات الواحدة تحت الأخرى، تحصل على جدول. ونحصل على الصيغة ${\displaystyle \varphi _{w$ التي ترمز لوجود جدول رموز محصل عن طريق الإعدادات المتتابعة لحساب مقبول ل w.

إعدادات	0	1	2	3	...	n^k
${\displaystyle C_{0 =$	${\displaystyle q_{0$	${\displaystyle W_{1$	${\displaystyle W_{2$	${\displaystyle W_{3$	...	#
${\displaystyle C_{1 =$	${\displaystyle W'_{1$	${\displaystyle q_{1$	${\displaystyle W_{2$	${\displaystyle W_{3$	...	#
${\displaystyle C_{2 =$	${\displaystyle W'_{1$	${\displaystyle W'_{2$	${\displaystyle q_{2$	${\displaystyle W_{3$	...	#
${\displaystyle C_{3 =$	...	...	...	...	...	#
...	...	...	...	...	...	#
${\displaystyle C_{n^{k$	...	...	...	...	...	...

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

عندنا العلاقة: ${\displaystyle \varphi _{w =\varphi _{cell \wedge \varphi _{start \wedge \varphi _{move \wedge \varphi _{accept$ حيث جميع من ${\displaystyle \varphi _{cell$ و ${\displaystyle \varphi _{start$ و ${\displaystyle \varphi _{move$ و ${\displaystyle \varphi _{accept$ ترمز لوجود مسار مقبول.

الحصول على الصيغة ${\displaystyle \varphi _{cell$

الصيغة ${\displaystyle \varphi _{cell \,$ هي صيغة عطف لكل خانة (i,j). وهي تضمن على الأقل حتى متغير ${\displaystyle X_{i,j,a \,$ له القيمة 1 لكن متغيران ${\displaystyle X_{i,j,a \,$ و ${\displaystyle X_{i,j,b \,$ لكل ${\displaystyle a\neq b\,$ لا يمكن حتىقد يكون لهما القيمة 1 في نفس الوقت.

الصيغة تخط على الشكل: ${\displaystyle \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]$

الحصول على الصيغة ${\displaystyle \varphi _{start$

تخط الصيغة هكذا: ${\displaystyle 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 يرمز ل #.

الحصول على الصيغة ${\displaystyle \varphi _{accept$

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

الصيغة تخط على الشكل: ${\displaystyle \varphi _{accept =\lor _{0\leq j\leq n^{k \;and\;{q\in F \;^{x \!n^{k ,j,q$

الحصول على الصيغة ${\displaystyle \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 : إيجاد قيم لمتغيرات ثنائية تجعل الصيغة العادية لعطف سليمة تضم جميع مجموعة ثلاثة عناصر.
CHROMATIC NUMBER : تحديد أصغر عدد تلوين مخطط حيث جميع قمتين مرتبطتينقد يكون لهما لونان مختلفان.
CLIQUE COVER :
EXACT COVER :
MATCHING à ثلاثة dimensions :
STEINER TREE :
HITTING SET :
KNAPSACK :
JOB SEQUENCING :
PARTITION :
MAX-CUT :