مسألة NP كاملة

من ويكيبيديا، الموسوعة الحرة

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

1. كل مسألة من NP، تختصر لمسألة NP.
2. المسألة NP.

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

فهرست 1 مبرهنة كوك و ليفين 1.1 مفهوم الإختصار 1.2 البرهنة 2 لائحة ب 21 مسألة NP كلاسيكية (كارب)

[تحرير] مبرهنة كوك و ليفين

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

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

[تحرير] مفهوم الإختصار

نقول أن A يتم اختصاره إلى B في وقت حدودي، في حالة وجود دالة قابلة للحساب في وقت حدودي، يحيث لكل , إذا و فقط إذا كان . نسمي الدالة دالة الإختصار, و خوارزمية حدودية التي تحسب يسمى خوارزمية الإختصار.

[تحرير] البرهنة

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

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

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

بالنسبة لكل خانة من الجدول و كل رمز a ، ندخل المتغير X_i,j,a الذي يرمز لكون الخانة تتضمن أو لا الرمز a. عدد هذه المتغيرات حدودي.

[تحرير] لائحة ب 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 :