Partial algebras and complexity of satisfiability and universal theory for distributive lattices, boolean algebras and Heyting algebras

Characterizations are given for the classes of partial subalgebras of distributive lattices, boolean algebras and Heyting algebras. Thereby, complexity results are obtained for the satisfiability of quantifier-free first-order sentences in these classes. Satisfiability is NP-complete for distributive lattices and boolean algebras, and for Heyting algebras is PSPACE-complete. Consequently, the universal theory of distributive lattices and of boolean algebras is co-NP-complete and the universal theory of Heyting algebras is PSPACE-complete.