Counting linear extensions (Q1183942): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 00:37, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Counting linear extensions |
scientific article |
Statements
Counting linear extensions (English)
0 references
28 June 1992
0 references
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)].
0 references
number of linear extensions
0 references
\(\# P\)-complete
0 references
3-SAT Count Problem
0 references
randomized algorithms
0 references
volume of a rational polyhedron
0 references