Counting linear extensions is #P-complete

Abstract

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.