الحد الأقصى لعدد الأدوات الحرفية الإيجابية في 2SAT

Question

max 2sat هو np كاملة.

بدلا من إرضاء الحد الأقصى لعدد البنود، لدي صيغة 2SAT الراضية تماما وأريد أن أحصل على الحد الأقصى لعدد الأدوات الإيجابية في المهمة (بحيث تكون جميع البنود راضية، بالطبع).

ما هي صعوبة هذه المشكلة؟

Answer 1

هذه المشكلة هي NP-Hard (وبالإضافة إلى الصعب التقريب و W [1] -Hard)، لأن الحد الأقصى للمجموعة المستقلة يمكن تخفيضها إليها.الحد: يمثل كل متغير قوستتكيا ويمثل كل جملة حافة.