Simpler Optimal Sorting from a Directed Acyclic Graph

Fredman proposed in 1976 the following algorithmic problem: Given are a ground set X, some partial order P over X, and some comparison oracle OL that specifies a linear order L over X that extends P. A query to OL has as input distinct x,x‘ ϵ X and outputs whether x <L x’ or vice versa. If we denote by e (P ) the number of linear orders that extend P, then it follows from basic information theory that log e (P ) is a worst-case lower bound on the number of queries needed to output the sorted order of X.