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

في البداية، مبرهنة كوك ليفين في نظرية التعقيد الحسابي تنص على أن مسألة الاكتفاء (SAT) هي NP كاملة، يعني أنَّ كل مسألة في NP يمكن اختصارها بوقت حدودي بواسطة آلة تيورنج قطعية حدودية لمسألة تحديد إذا ما صيغة بوليانية قابلة للاكتفاء . ونتناول فيما يلي مزيدًا من التفاصيل.
وفي السياق ذاته، أحد تبعات هذه المُبرهنة أنه لو وُجدت خوارزمية لحل مسألة الاكتفاء حينها كل لغة في NP يمكن كذلك حلها كذلك بواسطة نفس الخوارزمية وبوقت حدودي والامر ذاته كذلك لكل لغة تابعة ل- NP كاملة .
هذه المبرهنة سميت على اسم ستيفان كوك وليونيد ليفين.
وفي السياق ذاته، ايجاد هذه الخوارزمية أو برهان عدم وجودها كان الموضوع الاساسي في علم الحاسوب منذ 30 عام وهذه المسألة تسمى مسألة P=NP .
الحصول على الصيغة
مع ملاحظة أن D يرمز ل #.
تكتب الصيغة هكذا:
الحصول على الصيغة
من جهة ثانية، الصيغة هي صيغة عطف لكل خانة (i,j). وهي تضمن على الأقل أن متغير له القيمة 1 لكن متغيران و لكل لا يمكن أن يكون لهما القيمة 1 في نفس الوقت.
الصيغة تكتب على الشكل:
برهان
عندنا العلاقة: حيث كل من و و و ترمز لوجود مسار مقبول.
في هذا الإطار، A مسألة من صنف NP. هذه المسألة مقبولة من آلة تورنغ M غير محددة. بالنسبة لكل مداخلة w ل M، توجد صيغة ذات بعد حدودي بالنسبة لبعد w والتي تكون كافية إذا وفقط إذا كانت w مقبولة من M.
وفي هذا السياق، بالنسبة لكل خانة من الجدول مع و.و كل رمز ، ندخل المتغير الذي يرمز لكون الخانة تتضمن أو لا الرمز . عدد هذه المتغيرات حدودي.
إضافةً إلى ذلك، نرمز ل بعد w. بما أن الآلة M تعمل في وقت حدودي، يوجد عدد طبيعي ثابت k حيث كل عملية حسابية على w تكون على الأكثر بطول . نضيف سلسلة انتظار مغلقة، ونفترض أن طول العمليات هو بالضبط . آلة تورنغ تستعمل خلية. الإعدادات الخاصة بحساب مقبول يكون كذلك بطول . عند كتابة جميع الإعدادات الواحدة تحت الأخرى، تحصل على جدول. ونحصل على الصيغة التي ترمز لوجود جدول رموز محصل عن طريق الإعدادات المتتابعة لحساب مقبول ل w.
تعريفات
ومن ناحية أخرى، مسألة تقرير تابعة ل-NP إذا يوجد آلة تيورنج غير قطعية حدودية تقرر المسألة .
الحصول على الصيغة
- هذه الصيغة تضمن على الأقل أن أحد خانات السطر الأخير من الجدول يضم حالة نهائية.
- الصيغة تكتب على الشكل:
- مراجع
- انظر كذلك
- NP
- SAT
- مسألة P=NP
- مسألة NP كاملة
- نظرية التعقيد الحسابي
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟