هو رتيب 3-جلس مع بالضبط 3 متغيرات متميزة غير قابلة للحياة؟

Question

قد أعطيت اختلاف السبت التالي:

نظرا لصياغة F في CNF حيث يحتوي كل جملة ج C للضبط 3 حرفي متميز ولكل ج في F إما أن تكون جميع الحرفية إيجابية أو كل حرفي يتم إلغاؤها. مثال:

$ f= (x_1 \ vee x_2 \ vee x_4) \ edge (neg x_2 \ vee \ neg x_3 \ vee \ neg x_4) \ wedge (x_3 \ vee x_4 \ VEE X_5) $

هل هذا الاختلاف لسبت القاضي؟

النتائج الخاصة بي حتى الآن:

أظن أن المشكلة مكتملة NP وبالتالي غير قابلة للاستمرار. وبالتالي أود إجراء تخفيض بولي من 3-جلس التباين المذكورة أعلاه.

يمكن تحويل صيغة 3-Sat تعسفي إلى رتيبة 3-SAT.

اتخذ المثال التالي:

$ c_1= (x_1 \ vee x_2 \ vee \ neg x_3) $ وحدد $ z_3 $ بواسطة $ \ neg x_3 \ leftrightrogg z_3 $ و $ x_3 \ Leftrightrow \ Neg z_3 $ وهو ما يعادله إلى $ (x_3 \ vee z_3) \ Wedge (\ neg x_3 \ vee \ neg z_3) $ .

من ذلك نحصل على شكل رتيب من $ c_1 $ بواسطة

$ (x_1 \ vee x_2 \ vee \ neg x_3) \ leftrightrower (x_1 \ vee x_2 \ vee z_3) \ wedge (x_3 \ vee z_3) \ wedge (\ neg x_3 \ Vee \ Neg z_3) $

من خلال تطبيق هذا التحول إلى جميع البنود، أحصل على صيغة رتيبة 3-Sat مرضية بنفس القدر.

تخفيض بلدي ينتج 2 عبوات إضافية مع حرفين لكل بند غير رتابة، ولكن كيف يمكنني الحصول على بنود رتيب فقط مع الحرفيات المتميزة فقط؟

Answer 1

سأحاول الإجابة الآن على سؤالي الخاص وسأكون سعيدا ببعض الأعلاف المتعلقة بالفرضية.

كما هو الحال في السؤال المذكورة أعلاه وأشار من قبل كايل جونز يمكننا الحد من الصيغ المركزي 3-Sat إلى صيغ مونوتون 3-Sat.

على سبيل المثال جملة $ c= (x_1 \ vee x_2 \ vee \ neg x_3) $ يمكن تحويلها إلى $ c '(x_1 \ vee x_2 \ vee z_3) \ wedge (z_3 \ vee x_3) \ wedge (\ neg z_3 \ vee \ neg x_3) $ . يمكن للمرء التحقق مما إذا كان $ C $ هو راضي $ c '$ هو مريض أيضا وإذا كان $ C $ ليست راضية $ c '$ أيضا غير راض.

الخطوة التالية هي تحويل جميع البنود بأقل من 3 حرفي إلى الجمل مع 3 حرفي متميز بالضبط.

بالتالي تأخذ على سبيل المثال $ c_1= (x_1 \ vee x_2) $ وتحويلها إلى $ c_1 '= ( X_1 \ VEE X_2 \ VEE Y_1) \ Wedge (X_1 \ VEE X_2 \ VEE Y_2) \ Wedge (X_1 \ VEE X_2 \ VEE Y_3) \ Wedge (\ Neg y_1 \ Vee \ Neg y_2 \ Vee \ Neg y_3) $ ثم مرة أخرى إذا $ c_1 $ راضي $ c_1 '$ هو أيضا راضي وإذا كان $ c_1 $ غير راض $ c_1 '$ أيضا غير راض. نفس الشيء يمكن القيام به للحالة السلبية IE $ c_2= (\ neg x_1 \ vee \ neg x_2) $ يمكن تحويلها إلى $ c_2 '= (\ neg x_1 \ vee \ neg x_2 \ vee \ neg u_1) \ wedge (\ neg x_1 \ vee \ neg x_2 \ vee \ neg u_2) \ wedge (\ neg x_1 \ vee \ neg x_2 \ Vee \ Neg U_3) \ Wedge (U_1 \ Vee U_2 \ Vee U_3) $

من خلال تطبيق التحويلتين يمكن للمرء تحويل مثيل عشوائي عشوائي تعسفي إلى مثيل راتبي 3-Sat مع حرفي متميز بالضبط. كما يمكن أن نرى بسهولة فوق التحولات لها تعقيد متعدد الحدود. لذلك منذ 3 جلس هو NP-Hard، يجب أن يكون التخفيض ASWell NP-Hard.