On Ranking
Lane A. Hemachandra · 1987
This paper structurally characterizes the complexity of ranking. A set is P-rankable if there is a polynomial time computable function f so that for all x, f(x) computes the number of elements of A that are lexicographically ≤ x, i.e., the rank of χ with respect to A [GS85]. We'll say a class C is P-rankable if all sets in C are P-rankable. Our main results show that with the same certainty with which we believe counting to be complex, and thus with at least the certainty with which we believe P ≠ NP, we may believe that P has no uniform, strong, weak, or enumeratively approximate ranking functions.