هو التقليل من التعبيرات المنطقية-NP كاملة ؟

Question

وأنا أعلم أن منطقية satisfiability هو NP-Complete, ولكن هو تقليل/تبسيط تعبير منطقي ، الذي يعني أخذ معين التعبير في شكل رمزي و إنتاج ما يعادل ولكن تبسيط التعبير في شكل رمزي ، NP-كاملة ؟ أنا لست متأكدا من أن هناك انخفاضا من satisfiability إلى تقليل لكنني أشعر أن هناك على الأرجح.لا أحد يعرف على وجه اليقين ؟

Answer 1

حسنا, أنظر إلى الأمر بهذه الطريقة:باستخدام التقليل من الخوارزمية ، يمكنك ضغط أي غير قابل للإرضاء عربية التعبير الحرفي false, صحيح ؟ هذا بشكل فعال يحل السبت.لذا على الأقل كاملة التقليل من الخوارزمية لا بد أن يكون NP-complete NP صعبة.