In a poset $P$, $U\subseteq P$ is an upper set when for all $x\in U$, we have $y\ge x$ implies $y\in U$. Any subset of $P$ generates an upper set, and the basis of an upper set $U$ is the smallest set which generates it, or the set of minimal elements of $U$.

Similarly, a lower set which contains $x$ also contains all $y\le x$, and its basis is the set of its maximal elements. The complement of an upper set is always a lower set.

My question is: given the basis of an upper set in the poset $(2^{[n]},\subseteq)$, is there a good way to determine the basis of the lower set which is its complement? Can it be described with some mathematical formula, or is there at least an algorithm to do so that is asymptotically better than brute force?

  • 2
    $\begingroup$ The problem is equivalent to conversion of a monotone DNF to a monotone CNF. Since the output may be exponentially larger than the input, you cannot do better than exponential time. $\endgroup$ – Emil Jeřábek Oct 8 '14 at 9:26

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.