مسألة NP كاملة

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

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

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

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

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

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

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

نقول أن خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_1} يتم اختصاره إلى خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_2} في وقت حدودي، في حالة وجود دالة قابلة للحساب في وقت حدودي، خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle f : \left\{0,1\right\}^* \rightarrow \left\{0,1\right\}^*} يحيث لكل خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in \left\{0,1\right\}^*} , خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in L_1} إذا وفقط إذا كان خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) \in L_2} . نسمي الدالة خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle f\!} دالة الإختصار, وخوارزمية حدودية التي تحسب خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle f\!} يسمى خوارزمية الإختصار.

البرهنة

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

A مسألة من صنف NP. هذه المسألة مقبولة من آلة تورينغ M غير محددة. بالنسبة لكل مداخلة w ل M، توجد صيغة خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varphi_w } ذات بعد حدودي بالنسبة لبعد w والتي تكون كافية إذا وفقط إذا كانت w مقبولة من M.

نرمز ل خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=|w|} بعد w. بما أن الآلة M تعمل في وقت حدودي، يوجد عدد طبيعي ثابت k حيث كل عملية حسابية على w تكون على الأكثر بطول خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^k } . نضيف سلسلة انتظار مغلقة، ونفترض أن طول العمليات هو بالضبط خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^k } . آلة تورينغ تستعمل خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^k } خلية. الإعدادات الخاصة بحساب مقبول يكون أيضا بطول خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^k } . عند كتابة جميع الإعدادات الواحدة تحت الأخرى، تحصل على جدول. ونحصل على الصيغة خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varphi_w } التي ترمز لوجود جدول رموز محصل عن طريق الإعدادات المتتابعة لحساب مقبول ل w.

إعدادات	0	1	2	3	...	n^k
خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_0 = }	خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_0}	خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle W_1}	خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle W_2}	خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle W_3}	...	#
خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_1 = }	خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle W'_1}	خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_1}	خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle W_2}	خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle W_3}	...	#
خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_2 =}	خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle W'_1}	خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle W'_2}	خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_2}	خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle W_3}	...	#
خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_3 = }	...	...	...	...	...	#
...	...	...	...	...	...	#
خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_{n^k}}	...	...	...	...	...	...

بالنسبة لكل خانة خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle (i,j) \,} من الجدول مع خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \ge i} وخطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle j \le n^k} .و كل رمز خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \,} ، ندخل المتغير خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_{i,j,a} \,} الذي يرمز لكون الخانة تتضمن أو لا الرمز خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \,} . عدد هذه المتغيرات حدودي.

عندنا العلاقة: خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varphi_w = \varphi_{cell} \wedge \varphi_{start} \wedge \varphi_{move} \wedge \varphi_{accept}} حيث كل من خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varphi_{cell}} وخطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varphi_{start}} وخطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varphi_{move}} وخطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varphi_{accept}} ترمز لوجود مسار مقبول.

الحصول على الصيغة خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varphi_{cell}}

الصيغة خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varphi_{cell} \,} هي صيغة عطف لكل خانة (i,j). وهي تضمن على الأقل أن متغير خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_{i,j,a} \,} له القيمة 1 لكن متغيران خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_{i,j,a} \,} وخطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_{i,j,b} \,} لكل خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \ne b \,} لا يمكن أن يكون لهما القيمة 1 في نفس الوقت.

الصيغة تكتب على الشكل: خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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]}

الحصول على الصيغة خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varphi_{start}}

تكتب الصيغة هكذا: خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\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 يرمز ل #.

الحصول على الصيغة خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varphi_{accept}}

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

الصيغة تكتب على الشكل: خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varphi_{accept} = \lor_{0\le j\le n^k} \;and\; {q\in F}\; ^x\!n^k,j,q }

لائحة ب 21 مسألة NP كلاسيكية (كارب)

ملف:Relative NPC chart.png

المسائل الكلاسيكية

• 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
• إن بي