المحتوى هنا ينقصه الاستشهاد بمصادر، أي معلومات غير موثقة يمكن التشكيك بها وإزالتها.
يرجى مراجعة هذه المقالة وإزالة وسم المقالات غير المراجعة، ووسمها بوسوم الصيانة المناسبة.

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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
N write.svg
هذه مقالة غير مراجعة. ينبغي أن يزال هذا القالب بعد أن يراجعها محرر ما عدا الذي أنشأها؛ إذا لزم الأمر فيجب أن توسم المقالة بقوالب الصيانة المناسبة. (يوليو 2013)
Question book-new.svg
المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (مارس 2016)

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

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

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

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

تعريفات[عدل]

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

برهان[عدل]

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

نرمز ل بعد w. بما أن الآلة M تعمل في وقت حدودي، يوجد عدد طبيعي ثابت k حيث كل عملية حسابية على w تكون على الأكثر بطول . نضيف سلسلة انتظار مغلقة، ونفترض أن طول العمليات هو بالضبط . آلة تورينغ تستعمل خلية. الإعدادات الخاصة بحساب مقبول يكون أيضا بطول . عند كتابة جميع الإعدادات الواحدة تحت الأخرى، تحصل على جدول. ونحصل على الصيغة التي ترمز لوجود جدول رموز محصل عن طريق الإعدادات المتتابعة لحساب مقبول ل w.

إعدادات 0 1 2 3 ... n^k
... #
... #
... #
... ... ... ... ... #
... ... ... ... ... ... #
... ... ... ... ... ...

بالنسبة لكل خانة من الجدول مع و.و كل رمز ، ندخل المتغير الذي يرمز لكون الخانة تتضمن أو لا الرمز . عدد هذه المتغيرات حدودي.

عندنا العلاقة: حيث كل من و و و ترمز لوجود مسار مقبول.

الحصول على الصيغة [عدل]

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

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

الحصول على الصيغة [عدل]

تكتب الصيغة هكذا:

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

الحصول على الصيغة [عدل]

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

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

الحصول على الصيغة [عدل]

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