جلس الرضا عن 10 متغيرات

Question

أحاول إثبات أن المشكلة التالية هي NPC:

$$ a={\ langle \ phi \ rangle \ \ big |\ \ Phi \ \ text {هو cnf وجلس.المهمة حيث يوجد بالضبط 10 vars صحيح} \}

أحاول العثور على تخفيض التعيين متعدد الحدود من SAT لكن لا يمكنني العثور على طريقة لإجبار 10 متغيرات بالضبط للحصول على مهمة حقيقية. كانت فكرتي إنشاء صيغة جديدة، مع وجود 10 بنود، كل جملة هي تقاطع متغير جديد $ x_i $ مع الصيغة القديمة، لكنني لا أرى كيففكرتي مفيدة.

سأقدر المساعدة.

Answer 1

المشكلة التي ذكرتها هي في $ P $ لذلك فهي ليست كاملة NP.نحن نعلم أن $ | \ Phi |= N $ لذلك عدد المتغيرات أقل من $ n $ ، ونحن نعلم أن أعضاء $ a$ لديها بالضبط 10 مهام حقيقية.لذلك من خلال خوارزمية القوة الغاشمة تحقق من كل مهمة ممكنة للمتغيرات.اختر 10 متغيرات من N، $ (^ {n} _ {10}) $ وتعيينها إلى $ true $ وتعيين المتغيرات الأخرى إلى $ false $ وتحقق مما إذا كانت هذه مهمة مرضية.وقت التشغيل من هذه الخوارزمية هو $ (^ {n} _ {10}) * n= o (n ^ {11}) $ .