On the Computational Complexity of Algebra on Lattices
Harry B. Hunt, Daniel J. Rosenkrantz, Peter A. Bloniarz · SIAM Journal on Computing · 1987
We study the computational complexity of equivalence and minimization problems for expressions on many different lattices including each finite lattice and each distributive lattice. A general efficient expressibility condition C on a lattice is presented such that 1. The equivalence problem is co$NP$ hard for constant-free expressions on any lattice with at least two elements that satisfies condition C. Each finite or distributive lattice is shown to satisfy condition C. Moreover, if a lattice $\mathcal{L}$ satisfies condition C and $ \equiv $ is a congruence relation on $\mathcal{L}$, then ${\mathcal{L} / \equiv }$ also satisfies condition C. Several additional results are also presented. These results include the following: 2. In contrast to 1, the equivalence and operator minimization problems are solvable deterministically in polynomial time for disjunctive normal form and conjunctive normal form expressions on any lattice and for constant-free expressions on any free lattice with at least three generators: 3. Let $\mathcal{L}$ be a lattice. Then, the operator minimization problem and various approximate operator minimization problems for expressions on $\mathcal{L}$ are as hard as the problem of determining, for expressions F and G on $\mathcal{L}$, if $F \leqq G$.