Dualization in lattices given by implicational bases
share
It was recently proved that the dualization in lattices given by implicational bases is impossible in output-polynomial time unless P=NP. In this paper, we show that this result holds even when premises in the implicational base are of size at most two. In the case of premises of size one -- when the lattice is distributive -- we show that the dualization is possible in output quasi-polynomial time whenever the comparability graph of the poset coding the lattice is of bounded maximum induced matching. Lattices that share this property include distributive lattices coded by the ideals of an interval order.
READ FULL TEXT