ماكس 2-الساتان هو الوقت متعدد الحدود معلي ل 2-SAT؟

Question

أعرف أن 2-SAT قابلة للحل في وقت متعدد الحدود و 2-SAT هو NP-Hard.

لدي إصدار حول هذا البيان: ماكس 2 الساتان هو متعدد الحدود القابلة للاختزال 2-جلس.هل يمكن أن توضح لي كيف يبدو تخفيض؟أحتاج إلى التعرض الوحيد حول ذلك، ولكن ليس دليلا.

Answer 1

أعتقد أن هناك بعض الارتباك هنا.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 $ راضية.