تعقيد حالات محددة من max2sat

Question

أعرف أن Max2SAT هو NP-Complete بشكل عام، لكنني أتساءل حول ما إذا كان من المعروف أن بعض الحالات المحظورة معروفة في P. بالتأكيد اللغات

$ l_k:={\ phi \، text \ text {هو مثيل 2SAT الذي لديه مهمة مرضية على الأقل بنود K.} \ } $

يمكن حلها في

$ o (n ^ k) $ من خلال البحث عن القوة الغاشمة نظرا لكل لغة $ k $ ثابت. ومع ذلك، أتساءل عن القضية عند تحديد جزء بسيط من البنود. هل يحصل أي جزء عن مشكلة مشكلة NP؟ على وجه التحديد، أتساءل عن حالة إرضاء ما لا يقل عن نصف بنود مثيل 2SAT.

تخفيض رأيته من 3SAT إلى Max2SAT يبني 10 عبوات من كل بند في 3SAT مثل هذه العشرة، بالضبط 7 هي راضية عندما تكون جملة 3SAT الأصلية راضية وعلى الأكثر راضين عند عدم رضطة البند الأصلي وبعد لذلك في هذا الحد من جزء بسيط من $ 7/10 $ يعمل ولكن $ 1/2 $ لا لأن الحقيقة غير المرضية لا يزال يمكن إجراء مهام مثيل 3SAT على مثيل 2SAT له مهمة تلبي أكثر من نصف البنود. فكرت في بناء آخر أو إضافة جمل إضافية إلى مثيل 2SAT لكنني غير ناجح حتى الآن.

Answer 1

يمكنك دائما تلبية نصف البنود على الأقل: لكل متغير $ x $ ، ابحث عن عدد البنود التي تحتوي على $ x $ وعدد البنود التي تحتوي على $ \ lnot x $ . حدد الشخص الذي يرضي معظم البنود. إزالة البنود التي تحتوي على $ x $ و $ \ lnot x $ . كرر المتغيرات الأخرى.

منذ ذلك الحين بالنسبة لكل $ x $ نرضي ما لا يقل عن نصف البنود التي تمت إزالتها، ونحن ترضي نصف البنود بشكل عام.

من ناحية أخرى، فهي أيضا ضيقة: دع $ \ alpha> \ frac 12 $ يكون جزءا بسيطا يمكننا تقديم إجابة. دع $ \ beta> \ frac 12 $ يكون الحد الأقصى للكسر من البنود التي يمكننا إرضائها في جملة محددة. ثم يمكننا إضافة عبوات حتى تصبح $ \ beta $ (للفلة الجديدة) تصبح جملة تعسفية $ \ ألفا $ < / span>:

• إذا $ \ beta <\ alga $ ، ثم يمكننا إضافة جمل $ (x_i \ lor \ lnot x_i) $ ، حتى $ \ beta> \ alpha $ (نظرا لأن هذه الجمل هي دائما حقيقية، $ \ beta $ الزيادات).
• إذا كنت $ \ beta> \ alfa $ ، يمكننا إضافة جمل $ (x_i) $ و $ (\ lnot x_i) $ ، حتى $ \ beta <\ alpha $ (منذ نصف البنود بالضبط صحيح، $ \ beta $ النقصان).

لم أفحص، ولكن للحصول على $ O (\ FRAC 1M) $ الفرق (أي للعثور على العدد الدقيق من البنود)، وأعتقد أنه يكفي لإضافة $ o (m) $ clauses. وبعبارة أخرى، إذا استطعنا حلها لبعض $ \ alpha> \ frac 12 $ ، يمكننا التحقق من أي $ \ BETA $ سواء $ \ beta $ جزء من البنات يمكن أن يكون راضيا، وبالتالي يمكننا حل max2sat في وقت متعدد الحدود.