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?



Is every complete bounded finite lattice equivalent to a sublattice of a powerset lattice?
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$.


