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

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

مبرهنة كوك ليفين في نظرية التعقيد الحسابي تنص على أن مسألة الاكتفاء (SAT) هي NP كاملة , يعني أنَّ كل مسألة في NP يمكن اختصارها بوقت حدودي بواسطة الة تيورنج قطعية حدودية لمسألة تحديد اذا ما صيغة بوليانية قابلة للاكتفاء .

أحد تبعات هذه المُبرهنة أنه لو وُجدت خوارزمية لحل مسألة الاكتفاء حينها كل لغة في 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 \ge i وj \le 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 \ne b \, لا يمكن أن يكون لهما القيمة 1 في نفس الوقت.

الصيغة تكتب على الشكل: \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]

الحصول على الصيغة \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\le j\le n^k} \;and\; {q\in F}\; ^x\!n^k,j,q

الحصول على الصيغة \varphi_{move}[عدل]

انظر أيضا[عدل]