On the complexity of ranking

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

zbMATH Keywords

rankingKolmogorov complexityprintability

Mathematics Subject Classification ID

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 (12)

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the complexity of ranking