Deje $(P, \le)$ ser un poset en $n$ elementos $x_1\dots x_n$. Un orden total $<$ en el mismo conjunto se dice que es una extensión lineal de $\le$ si $(\forall i,j)\quad x_i \le x_j \rightarrow x_i < x_j$.
El problema de contar el número de lineal extensiones de un poset es conocido por ser $#P-complete$: esto queda demostrado en Brightwell, Graham R.; Winkler, Pedro (1991), "el cálculo lineal extensiones", Orden 8 (3): 225-242.
En el mismo papel de algunos límites son dados para estimar este número. Estos límites se han mejorado en Kahn, J.; Kim, J. H. (1992), "la Entropía y clasificación", Proocedings de la 24 ª reunión Anual de la ACM Simposio sobre Teoría de la Computación: 178-187
Fueron estos límites mejoró de nuevo? ¿Cuáles son los más conocidos de los límites para este problema?
