On the complexity of ranking
From MaRDI portal
Publication:920620
DOI10.1016/0022-0000(90)90038-MzbMath0708.68020OpenAlexW1975123488MaRDI QIDQ920620
Steven Rudich, Hemaspaandra, Lane A.
Publication date: 1990
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(90)90038-m
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Scalability and the isomorphism problem ⋮ Recursion-theoretic ranking and compression ⋮ On sets polynomially enumerable by iteration ⋮ Polynomial-time compression ⋮ A very hard log-space counting class ⋮ Closure and nonclosure properties of the classes of compressible and rankable sets ⋮ Characterizing the existence of one-way permutations ⋮ The enumerability of P collapses P to NC ⋮ All superlinear inverse schemes are coNP-hard ⋮ Tally NP sets and easy census functions. ⋮ Optimal series-parallel trade-offs for reducing a function to its own graph ⋮ The complexity of computing maximal word functions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Some consequences of non-uniform conditions on uniform classes
- Random generation of combinatorial structures from a uniform distribution
- Continuous optimization problems and a polynomial hierarchy of real functions
- NP is as easy as detecting unique solutions
- Complexity classes without machines: on complete languages for UP
- On sparse oracles separating feasible complexity classes
- On counting problems and the polynomial-time hierarchy
- The polynomial-time hierarchy
- Computation times of NP sets of different densities
- Complexity of Presburger arithmetic with fixed quantifier dimension
- Sets with small generalized Kolmogorov complexity
- Enumerative counting is hard
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- On Approximation Algorithms for # P
- The Complexity of Enumeration and Reliability Problems
- Computational Complexity of Probabilistic Turing Machines
- Relativized Polynomial Time Hierarchies Having Exactly K Levels
- P-Printable Sets
- Computational Work and Time on Finite Machines
- The complexity of theorem-proving procedures
This page was built for publication: On the complexity of ranking
