Boole ifadelerinin en aza indirgenmesi NP-Complete?

Question

Boole memnuniyetinin NP-Complete olduğunu biliyorum, ancak sembolik formda belirli bir ifadeyi almak ve sembolik formda bir eşdeğer ancak basitleştirilmiş ifade, NP-Complete üretmek anlamına gelen bir boole ifadesinin en aza indirilmesi/basitleştirilmesi mi? En aza indirgemeye karşı tatmin edici bir azalma olduğu konusunda emin değilim, ama muhtemelen varmış gibi hissediyorum. Emin olan birileri var mı?

Answer 1

Peki, şu şekilde bakın: en aza indirgeme algoritması kullanarak, herhangi bir tatmin edici olmayan ifadeyi literal false, ile birleştirebilirsiniz, değil mi? Bu, SAT'yi etkili bir şekilde çözer. Bu nedenle, en azından tam bir küçültme algoritması, NP-tam NP sert olmak zorundadır.