Hardness of Counting Orderings: Taking Gadget Amplification to the LimitResearch Paper
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…