ماكس 2-الساتان هو الوقت متعدد الحدود معلي ل 2-SAT؟
-
29-09-2020 - |
سؤال
أعرف أن 2-SAT قابلة للحل في وقت متعدد الحدود و 2-SAT هو NP-Hard.
لدي إصدار حول هذا البيان: ماكس 2 الساتان هو متعدد الحدود القابلة للاختزال 2-جلس.هل يمكن أن توضح لي كيف يبدو تخفيض؟أحتاج إلى التعرض الوحيد حول ذلك، ولكن ليس دليلا.
المحلول
أعتقد أن هناك بعض الارتباك هنا.MAX-2-SAT هو NP-Hard (ونسخة القرار الخاصة به كاملة)، في حين أن 2-SAT موجود في P وبالتالي أيضا في NP.هذا يعني أن 2-SAT هو متعدد الحدود القابلة للاختزال (إصدار القرار من) Max-2-Sat.العكس ليس صحيحا إلا إذا كان P= NP.
دع $ \ phi $ تكون صيغة 2-SAT مع $ m $ clauses. إذا كنت ترغب حقا في تقليل مثيل $ \ Phi $ من 2-SAT إلى (إصدار القرار من) Max-2-SAT، ثم هذا ببساطة المبالغ لفحص ما إذا كانعلى الأقل $ m $ (أي، الكل) بنود $ \ Phi $ راضية.
لا تنتمي إلى cs.stackexchange