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

مبرهنة كوك ليفين في نظرية التعقيد الحسابي تنص على أن مسألة الاكتفاء (SAT) هي NP كاملة، يعني أنَّ كل مسألة في NP يمكن اختصارها بوقت حدودي بواسطة آلة تيورنج قطعية حدودية لمسألة تحديد إذا ما صيغة بوليانية قابلة للاكتفاء .^[1]^[2]^[3]

أحد تبعات هذه المُبرهنة أنه لو وُجدت خوارزمية لحل مسألة الاكتفاء حينها كل لغة في NP يمكن أيضا حلها كذلك بواسطة نفس الخوارزمية وبوقت حدودي والامر ذاته أيضا لكل لغة تابعة ل- NP كاملة .

ايجاد هذه الخوارزمية أو برهان عدم وجودها كان الموضوع الاساسي في علم الحاسوب منذ 30 عام وهذه المسألة تسمى مسألة P=NP .

هذه المبرهنة سميت على اسم ستيفان كوك وليونيد ليفين.

تعريفات

مسألة تقرير تابعة ل-NP إذا يوجد آلة تيورنج غير قطعية حدودية تقرر المسألة .

برهان

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$

مراجع

^ Garey، Michael R.؛ David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. ISBN:0-7167-1045-5. مؤرشف من الأصل في 2019-12-16.
^ T. P. Baker؛ J. Gill؛ R. Solovay (1975). "Relativizations of the P = NP question". SIAM Journal on Computing. ج. 4 ع. 4: 431–442. DOI:10.1137/0204037.
^ Cook، Stephen (1971). "The complexity of theorem proving procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. ص. 151–158. DOI:10.1145/800157.805047.

انظر أيضا

[1] Garey، Michael R.؛ David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. ISBN:0-7167-1045-5. مؤرشف من الأصل في 2019-12-16.

[2] T. P. Baker؛ J. Gill؛ R. Solovay (1975). "Relativizations of the P = NP question". SIAM Journal on Computing. ج. 4 ع. 4: 431–442. DOI:10.1137/0204037.

[3] Cook، Stephen (1971). "The complexity of theorem proving procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. ص. 151–158. DOI:10.1145/800157.805047.

[1]

[2]

[3]