مسألة NP كاملة

من موسوعة العلوم العربية
اذهب إلى: تصفح، ابحث

قالب:مسألة NP كاملة في الرياضيات صنف التعقيد، تُعرف المسائل 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 \ge i
وخطأ رياضيات (خطأ غير معروف): j \le n^k

.و كل رمز خطأ رياضيات (خطأ غير معروف): a \, ، ندخل المتغير خطأ رياضيات (خطأ غير معروف): X_{i,j,a} \,

الذي يرمز لكون الخانة تتضمن أو لا الرمز خطأ رياضيات (خطأ غير معروف): a \,

. عدد هذه المتغيرات حدودي.

عندنا العلاقة: b5f10945c85acf9ca2aa32f5857c60aa- حيث كل من خطأ رياضيات (خطأ غير معروف): \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 في نفس الوقت.

الصيغة تكتب على الشكل: 51b4345975b527c62425cb05f1607828-

الحصول على الصيغة خطأ رياضيات (خطأ غير معروف): \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}

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

الصيغة تكتب على الشكل: 9d594ee2c6cd0305ab280b742676d4b0-

الحصول على الصيغة خطأ رياضيات (خطأ غير معروف): \varphi_{move}

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

أنظر أيضا