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

من أرابيكا، الموسوعة الحرة
اذهب إلى التنقل اذهب إلى البحث
قبول الحساب بطريقة مخططة بواسطة الآلة M

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

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

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

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

تعريفات

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

برهان

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

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

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

عندنا العلاقة: φw=φcellφstartφmoveφaccept حيث كل من φcell وφstart وφmove وφaccept ترمز لوجود مسار مقبول.

الحصول على الصيغة φcell

الصيغة φcell هي صيغة عطف لكل خانة (i,j). وهي تضمن على الأقل أن متغير Xi,j,a له القيمة 1 لكن متغيران Xi,j,a وXi,j,b لكل ab لا يمكن أن يكون لهما القيمة 1 في نفس الوقت.

الصيغة تكتب على الشكل: φcell=0i,jnk[(aAXi,j,a)(ab¬(Xi,j,aXi,j,b))]

الحصول على الصيغة φstart

تكتب الصيغة هكذا: x0,0,q0x0,1,w1x0,2,w2...x0,n,wnx0,n+1,D...x0,nk,D

مع ملاحظة أن D يرمز ل #.

الحصول على الصيغة φaccept

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

الصيغة تكتب على الشكل: φaccept=0jnkandqFxnk,j,q

مراجع

  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.

انظر أيضا