Counting number of permutations respecting partial order

Question

Suppose that we have an array $A$ of $n$ elements with some partial order known, e.g. for example as a $n\times n$ matrix containing $c_{ij} \in \{-1, 0, 1\}$ where $0$ represents unknown and $-1, 1$ represent $A_i < A_j$ and $A_i \geq A_j$ respectively.

Is there an efficient algorithm that counts the number of partitions of $A$ that respect the partial order? E.g. for the all-zero matrix (totally undefined partial order) it's simply $n!$ and for a matrix containing a total order it's simply $1$.

We can assume that the partial order does not contain contradictions, e.g. we won't have $A_i < A_i$ or some chain of comparisons that violates transitivity.

Answer 1

Brightwell and Winkler proved that this program is #P-complete in their paper Counting linear extensions. You can, however, estimate the number of linear extensions efficiently.