A linear extension of a finite partially ordered set (poset) is an ordering of its elements in which every element comes after all of its predecessors. Counting them, , is a basic problem of order theory with uses in sorting under partial information, scheduling, and Bayesian inference over orderings. Brightwell and Winkler proved in 1991 that computing is #P-complete for general posets (BW91), and Dittmer and Pak showed in 2020 that hardness already holds for posets of height 2 (DP20).
The class of N-free posets behaves differently. Introduced by Grillet (1969), it has a linear-time recognition and decomposition algorithm (Habib and Jégou, 1985) and generalizes series-parallel posets, on which counting linear extensions is easy. Felsner and Manneville (FM15) showed that counting is polynomial-time for N-free posets of height 2, left the general case open, and conjectured #P-completeness, suggesting that height 3 should already be hard. The question was recorded again in the survey of Chan and Pak (CP25, §12.1).
Timeline:
Let be a finite poset with order . An element covers , written , if and nothing lies strictly between them; the covers are the edges of the Hasse diagram. is N-free if there are no pairwise distinct with
that is, the Hasse diagram has no induced copy of the letter N. The height of is the maximum number of elements in a chain. is the number of bijections with .
An input is a bit string. A poset on is coded by its order matrix, read row by row: the bit at position is exactly when . The counting function of the mission is
A function is in #P if is the number of certificates accepted by a polynomial-time verifier. A function is #P-hard under polynomial-time Turing reductions if every #P function, with its values written in binary, can be computed in polynomial time by an oracle Turing machine whose oracle returns the target function's values in binary, each call costing one step. #P-complete means both.
The goal fixes the class exactly: N-free in the cover-graph sense above, and height exactly 3.
The milestones follow the paper's proof, a reduction from #X3C: an instance consists of a universe with and -element sets ; an exact cover is a choice of sets whose union is , and is their number. From and an integer the paper builds a directed acyclic graph whose edge poset (edges ordered by directed paths) is N-free of height 3. is a set of distinguished edges, the admissible orderings of , integers read off from , , and the orderings that end with the edges of the exact cover .
The result. Theorem 6.3 settles the Felsner–Manneville conjecture and places the complexity boundary for N-free posets exactly between height 2 (polynomial) and height 3 (#P-complete). Exact counting on this class therefore needs a different restriction than height, and approximate counting becomes the relevant question. The same paper uses the technique (gadget amplification with algebraic extraction of the count) for peeling sequences, successive vertex orderings and graph shellings.
Formalizing it. The theorem is proved on paper but has not been machine-checked, and the platform has no machine-checked #P-hardness result for any counting problem on posets. A formal proof needs: the hook-length formula for tree posets; an exact rational-function identity for in ; a limit computation at the pole ; polynomial-time recovery of a rational function from polynomially many oracle values; polynomial-time constructions on the published Cook–Levin machine model; and a #P-hard source problem. The paper cites #X3C, which is #P-complete under parsimonious reductions (Hunt, Marathe, Radhakrishnan and Stearns, 1998); no #P-hard base problem has a machine-checked proof on the platform yet.
The obvious reduction does not work. Linear extensions of include orderings that do not encode exact covers, and as every ordering contributes at the same rate , so the leading behaviour at infinity cannot separate exact covers from the rest. The count has to be read off near the finite point , where exact-cover orderings have poles of the largest order; that is a statement about a rational function of that is only observed at positive integers. The constructed posets must at the same time stay N-free and of height exactly 3, which rules out the usual amplification gadgets. On the formal side, the hardness half needs explicit oracle Turing machines with polynomial step bounds, including polynomial-time interpolation and exact rational arithmetic.
PartialOrder; covers are Mathlib's CovBy. N-freeness is the cover-graph pattern (, , , , pairwise distinct), not a condition on comparability. Height counts elements of a chain, not edges, and the goal uses height exactly 3.FCP.Order.LinearExtensions).NQueensComp.NPC.InSharpP; hardness is ExactAmpDich.SharpPHardT applied to , with polynomial-time Turing reductions on the published Cook–Levin oracle machines (one step per oracle call).namespace CountOrderings.NFree
theorem theorem_6_3 :
NQueensComp.NPC.InSharpP nfreeHeight3LinExtCount ∧
ExactAmpDich.SharpPHardT (fun x => NPBinary.encodeNat (nfreeHeight3LinExtCount x)) := by sorry
end CountOrderings.NFree
Let send the binary code of a finite poset that is N-free (its Hasse diagram has no induced copy of the pattern , , ) and has height exactly 3 (its longest chain has three elements) to the number of its linear extensions, and every other string to (definition CountOrderings.NFree.Encoding; a poset on elements is coded by its order matrix). Then is #P-complete:
Membership means that is the number of certificates accepted by a polynomial-time verifier (NQueensComp.NPC.InSharpP). Hardness means that every function in #P, with its value written in binary, is computed by a polynomial-time oracle Turing machine that queries with answers written in binary (ExactAmpDich.SharpPHardT applied to ).
This settles a conjecture of Felsner and Manneville (2015): counting linear extensions is polynomial-time for N-free posets of height 2, and the theorem shows that height 3 already makes it #P-complete.
Formalization Note. "Polynomial time" is a bound on the number of steps of a multi-tape Turing machine of the published Cook–Levin library; an oracle call costs one step. The hardness is under Turing reductions, not parsimonious ones.
Differences from the source:
InSharpP f ∧ SharpPHardT (bin ∘ f) with the published Cook–Levin machine model, oracle machines and binary numbers; reason: the paper's notions (#P membership, hardness under polynomial-time Turing reductions, p. 5) in the platform's published definitions.No open leaves. Every sub-goal is proved or awaiting decomposition.