Counting linear extensions is #P-complete
Graham Brightwell, Peter M. Winkler · 1991
We show that the problem of counting the number of linear extensions of a given partially ordered set is #P-complete.This settles a long-standing open question and contrssts with recent results giving randomized polynomial-time algorit hms for estimating the number of linear extensions.One consequence is that computing the volume of a rational polyhedron is strongly #P-hard.We also show that the closely related problems of determining the average height of an element c of a given poset, and of determining the probability that z lies below y in a random linear extension, are #P-complete.