What is the computational complexity of expression minimization over a distributive lattice?

43 Views Asked by At

If we start with Boolean algebra and eliminate the negation operation, making it monotone, we get a free distributive lattice ('$\mathrm{M}$' in Post's classification).

I'm curious about the effect on questions of complexity. CNF-SAT becomes trivial, so what about something more interesting, the Minimum Equivalent Expression problem? While the decision problem version for ordinary Boolean formulae is $\Sigma_2^\mathrm{P}$-complete, I think that corollary 2.8 from (1) shows MEE to be $\Pi^\mathrm{P}_1$-hard in the monotone case; is that correct? And is that the most accurate bound we have?


(1) Edith Hemaspaandra and Henning Schnoor. 2011. Minimization for generalized Boolean formulas. In Proceedings of the Twenty-Second international joint conference on Artificial Intelligence - Volume Volume One (IJCAI'11). AAAI Press, 566–571.