A partial order or poset P=(X, <) on a (finite) base set X determines the set L(P) of linear extensions of P. The problem of computing,
for a poset P, the cardinality of L(P) is #P-complete. A set {P1,P2,...,Pk} of posets on X covers the set of linear orders that is the
union of the L(Pi). Given linear orders L1,L2,...,Lm on X, the Poset Cover problem is
to determine the smallest number of posets that cover {L1,L2,...,Lm}. Here, we show that the
decision version of this problem is NP-complete. On the positive side, we explore
the use of cover relations for finding posets that cover a set of linear orders
and present a polynomial-time algorithm to find a partial poset cover.