Graph entropy and quantum sorting problems
Andrew Chi-Chih Yao · 2004
Let P = (X, 0 are constants and e(P) is the number of linear orderings consistent with P. Our proof builds on an interesting connection between sorting and Korner's graph entropy that was first noted and developed by Kahn and Kim (JCSS 51(1995), 390--399).