JavaScript is disabled for your browser. Some features of this site may not work without it.

## On Ranking

#####
**Author**

Hemachandra, Lane A.

#####
**Abstract**

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 $\leq x$, i.e., the rank of $x$ with respect to $A$. 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 $\neq$ NP, we may believe that P has no ranking functions of any type - uniform, strong, weak, or approximate. We show that: P and NP are equally likely to be P-rankable. P is P-rankable if and only if $P = P^{#P}$. This extends important work of Blum and Sipser [Sip85]. Even weak variations of P-ranking are hard if $P \neq P^{#P}$. PSPACE is P-rankable if and only if P = PSPACE. If P has small ranking circuits, then it has small ranking circuits of relatively low complexity. If P has small ranking circuits then the power of counting falls into the polynomial hierarchy (i.e., $P^{#P} \subseteq \(\sum_{2}^{p})\ = PH$). P/poly, the class of sets with small circuits is not P-rankable. P/poly has small ranking circuits if and only if $P^{#P}$/poly = $P^{#P/poly}$ = P/poly. If P is rankable, then P/poly has small ranking circuits. This links the ranking complexity of uniform and nonuniform classes. The ranks of some strings in easy sets are of high relative time-bounded Kolmogorov complexity unless P = $P^{#P}$. It follows that even approximate ranking is hard unless P = $P^{#P}$. This partially resolves a question posed by Sipser [Sip85, pp. 447-448].

#####
**Date Issued**

1986-12#####
**Publisher**

Cornell University

#####
**Subject**

computer science; technical report

#####
**Previously Published As**

http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR86-794

#####
**Type**

technical report