Résumé
A well-known method to represent a partially ordered set P (order for short) consists in associating to each element of P a subset of a ?xed set S = {1, . . . , k} such that the order relation coincides with subset inclusion. Such an embedding of P into 2S (the lattice of all subsets of S) is called a bit-vector encoding of P. In this article, we focus on computational complexity results. After a synthesis of known results, we come back on the NP-completeness by detailing a proof and enforcing the conclusion with non-approximability ratios. Besides this general result, we investigate the complexity of the 2-dimension for the class of trees. We describe a 4-approximation algorithm for this class. It uses an optimal balancing strategy which solves a conjecture of [KVH97]. Several interesting open problems are listed.