On the complexity of ranking
From MaRDI portal
Publication:920620
DOI10.1016/0022-0000(90)90038-MzbMath0708.68020MaRDI QIDQ920620
Hemaspaandra, Lane A., Steven Rudich
Publication date: 1990
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)
03D15: Complexity of computation (including implicit computational complexity)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
On sets polynomially enumerable by iteration, Polynomial-time compression, A very hard log-space counting class, The complexity of computing maximal word functions, Scalability and the isomorphism problem, Characterizing the existence of one-way permutations, Tally NP sets and easy census functions., Optimal series-parallel trade-offs for reducing a function to its own graph, The enumerability of P collapses P to NC, All superlinear inverse schemes are coNP-hard