هل هناك خوارزمية للحد من CNFS أكثر

Question

لدي صيغة منطقية في النموذج الطبيعي الملتحمة (CNF): $ (a \ vee b \ vee c) \ Wedge (a \ vee b \ vee \ neg cy) \ wedge (x \ vee y) $

أعلم أنه يمكن تبسيط ذلك إلى: $ (a \ vee b) \ wedge (x \ vee y) $ .

a) هل هناك خوارزمية لتحديد ما إذا كانت CNF موجودة بالفعل في النموذج المخفض أم لا؟

b) هل هناك خوارزمية يمكنها القيام بهذا التخفيض بطريقة أكثر كفاءة من مقارنة كل زوج من الجمل لمعرفة ما إذا كان يمكن تخفيض أي إقران؟أود أن أتمتة هذا الحد من أي CNF ويبحث عن أي خوارزميات يمكنني استعارة / تنفيذها.

Answer 1

CNF التقليل صعب؛انظر https://cstheory.stackexchange.com/q/9839/5038 .من المؤكد أن NP-Hard، وهناك شعور به "أكثر صعوبة".

طريقة واحدة للحصول على بعض الحدس لماذا من الصعب أن يكون ذلك إذا كان CNF غير راض، ثم شكله المخفض هو "خطأ"، في حين أنه إذا كان راضيا، فإن شكله المخفض هو شيء آخر.لذلك، إذا كان لديك وسيلة فعالة لإيجاد نموذج مخفض، فمن شأنه أن يمنحك فورا طريقة لمعرفة ما إذا كانت CNF راضية - وهي مهمة تعرفها هي NP-Hard.

شاهد https://cstheory.stackexchange.com/q/9839/5038 و