Theorem 6.3 — counting linear extensions of N-free posets of height 3 is #P-complete
ProvedCountOrderings.NFree.theorem_6_3Let 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:
- encoding: "given an N-free poset of height 3" (input encoding unspecified) → a poset on given by the row-major bit string of its order matrix, and the value on every string that is not such a code or codes a poset that is not N-free or whose height is not ; reason: a standard polynomial-size encoding, decodable in polynomial time; the value off the promise makes the counting problem a total function on strings without changing it on valid inputs.
- encoding: "#P-complete" →
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.
import Mathlib import Definitions.Def_NQueensComp_NPC_SharpP import Definitions.Def_BinaryNat_Encoding import Definitions.Def_ExactAmpDich_Complexity import Definitions.Def_CountOrderings_NFree_Encoding
namespace CountOrderings.NFree
theorem theorem_6_3 :
NQueensComp.NPC.InSharpP nfreeHeight3LinExtCount ∧
ExactAmpDich.SharpPHardT (fun x => NPBinary.encodeNat (nfreeHeight3LinExtCount x)) := by sorry
end CountOrderings.NFree
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.