Geek Answers Handbook

Minimizing Boolean Expressions NP-Complete?

I know that the logical feasibility is NP-Complete, but is the minimization / simplification of the Boolean expression, by which I mean accepting this expression in symbolic form and creating an equivalent but simplified expression in symbolic NP-Complete form? I'm not sure there is a reduction from feasibility to minimization, but I feel that there is probably. Does anyone know for sure?

+5
source share
1 answer

Well, look at it this way: using the minimization algorithm, you can combine any impossible expression with a literal one false, right? It effectively solves SAT. Thus, at least the complete minimization algorithm should be NP-complete NP hard.

+7
source

More articles:


All Articles