3
$\begingroup$

More precisely, if I have a complete bounded finite lattice $C$, can I compute a lattice-operation-preserving map $C \to P(S)$? for some $S$. If not, is there another universal lattice structure that has efficient meet and join implementations on a computer?

$\endgroup$
  • 3
    $\begingroup$ $\def\meet{\wedge}\def\join{\vee}$No, the operations in $P(S)$ are distributive (meaning that $x \meet (y \join z) = (x \meet y) \join (x \meet z)$ and vice versa) and this is not true in a general lattice. $\endgroup$ – David E Speyer Aug 6 '18 at 23:10
  • $\begingroup$ I think your general question about efficient implementation is an interesting one, but needs some thought to make precise. Afterall, a look up table is polynomial size in the number of entries of the lattice, so you have to answer "polynomial in what" for this to be a good question. $\endgroup$ – David E Speyer Aug 6 '18 at 23:12
  • 3
    $\begingroup$ I would consider partition lattices in place of power set lattices. $\endgroup$ – Keith Kearnes Aug 6 '18 at 23:13
  • $\begingroup$ Finite lattices are bounded and complete. They are not all distributive though, which is what you would need for C for an injective map from C into a power set lattice. (One C that does not work has three elements every two of which join to 1 and meet to 0.). There may be decent implementations of general lattices for computer manipulation, but you would have to search for them. Gerhard "Lattice Be Thankful For Indexes" Paseman, 2018.08.06. $\endgroup$ – Gerhard Paseman Aug 6 '18 at 23:15
  • 1
    $\begingroup$ Building on what @KeithKearnes mentioned, every finite lattice embeds in a partition lattice of a finite set, as shown here. Whether there is some useful computable implementation is another issue though. $\endgroup$ – Michael Greinecker Aug 6 '18 at 23:23
1
$\begingroup$

This answer addresses the vague question "is there another universal lattice structure that has efficient meet and join implementations on a computer?" The question of whether boolean lattices work has already been addressed in comments.

It is important to be clear what efficient means here. If we just want lattice operations to be polynomial in $|L|$, we can just use a $|L| \times |L|$ look up table.

I suspect the intent of the question is to encode elements of $L$ using polylog of $|L|$ bits, and perform operations in polylog of $|L|$ time. I will show that this is impossible. Namely, I will show that, for any subset $W$ of $2^{[n]}$, there is a lattice $L$ of size at most $4^n$ such that computing joins in $L$ is equivalent to testing membership in $W$. Diagonalization shows that some $W \subset 2^{[n]}$ cannot be tested in $O(n^k)$, so there must be some lattice that is hard to compute in.

So, the construction. Let $X \subset 2^{[2n]}$ be those binary words of length $2n$ which are of the form $w \bar{w}$ for $w \in W$, where $\bar{w}$ is the bit complement. So every element in $X$ has $n$ zeroes and $n$ ones. Let $L$ consist of the following binary strings of length $2n$:

  • all strings with $<n$ ones
  • the strings in $X$
  • the string $111 \cdots 1$.

Then it is easy to check that $L$ is a lattice under bitwise comparison; the $\vee$ operation is bitwise $\min$. Now consider computing the joint $(w 0^n) \join (0^n \bar{w})$. This will be $(w \bar{w})$ if $w \in W$, and will be $1^{2n}$ otherwise. So computing joins is equivalent to testing membership in $W$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.