On the complexity of ranking

摘要

This paper structurally characterizes the complexity of ranking. A set A is (strongly) 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 x with respect to A. This is the strongest of three notions of P-ranking we consider in this paper. We 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, P has no uniform, strong, weak, or enumerative ranking functions. We show that: 1.• P and NP are equally likely to be P-rankable, i.e., P is P-rankable if and only if NP is P-rankable.2.• P is P-rankable if and only if P = P#P. This extends work of Blum, Goldberg, and Sipser.3.• Even the two weaker notions of P-ranking that we study are hard if P ≠ P#P.4.•If P has small ranking circuits, then it has small ranking circuits of relatively low complexity.5.• If P has small ranking circuits then counting is in the polynomial hierarchy, i.e., P#P ⊆Σ2p = PH.6.• P/poly has small ranking circuits if and only if P#P/poly = P#P/poly = P/poly.7.• If P is P-rankable, then P/poly has small ranking circuits. This links the ranking complexity of uniform and nonuniform classes.8.• The ranks of some strings in easy sets are of high relative time-bounded Kolmogorov complexity unless P = P#P. It follows that even a type of approximate ranking, enumerative ranking, is hard unless P = P#P.9.• The complexity of generating “the next largest” element in a set has clear structural characterizations. In particular, (1) we can efficiently find some element of polynomial hierarchy sets at an input length if and only if P = PH ∩ P/poly, and (2) we can efficiently find some element of a polynomial hierarchy set greater than an input if and only if all sets in NP have infinite P-printable subsets.