Counting linear extensions (Q1183942): Difference between revisions

The problem of counting all linear extensions of a poset \(P\) (whose number is denoted by \(N(P)\)) is known to be very difficult, and in computer science it is important, e.g. in sorting algorithms. Although there exist polynomial algorithms for computing \(N(P)\) for certain special classes of posets, and even randomized polynomial-time algorithms, for the entire class of posets, for estimating \(N(P)\) with an arbitrary given approximation, it has been conjectured that this counting problem is \(\# P\)-complete (in the sense of L. G. Valiant). The authors solve the conjecture affirmatively, in fact only for posets of height at most 5 (the construction may be modified so as to get the height down to 3, but it seems that for posets of height 2, a different one is needed). The proof consists in a ``reduction'' of the given problem to the 3-SAT Count Problem, showing that, with the help of an oracle which counts linear extensions, a Turing machine can count the number of satisfying assignments to an instance of 3-SAT in polynomial time. The paper is also a valuable survey of the existing randomized algorithms for estimating \(N(P)\) and it discusses some consequences of the proven result on other related problems (e.g. the problem of computing the volume of a rational polyhedron). Much of this work has previously been published as an extended abstract [``Counting linear extensions is \(\# P\)-complete'', Proc. 23 rd ACM Symp. Theory of Computing, 175-181 (1991)].