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.
No takes yet. Share an insight, caveat, or question.
Brightwell et al. (1991) studied this question.