
A wellknown method to represent a partially ordered set consists in associating to each element of P a subset of a fixed set S={1,..,k} such that the order relation coincides with subset inclusion. Given an order P, minimizing the size of the encoding, i.e. the cardinal of S, is however a difficult problem. The smallest size is called the 2dimension of P. The paper details a proof that computing 2dimension of a given poset is NPC. Reduction allows to prove the nonapproximability of the problem. Later on the complexity of the 2dimension for the class of trees is investigated. Authors present a 4approximation algorithm for this class. References: M. Habibb, L. Nourinea, O. Raynauda and E. Thierry, Computational aspects of the 2dimension of partially ordered sets, Theoretical Computer Science 312 (2004), 401431 