On the complexity of ranking
From MaRDI portal
The rank function of a set of strings A is, on input x, the number of elements that are less or equal to x in lexicographic order. The paper analyzes the consequences of certain intractable complexity classes being P-rankable (meaning that the rank function is computable in polynomial time). Questions of this type are connected by logical implications or equivalences to other open problems in complexity theory.
Recommendations
Cites work
- Complexity classes without machines: on complete languages for UP
- Complexity of Presburger arithmetic with fixed quantifier dimension
- Computation times of NP sets of different densities
- Computational Complexity of Probabilistic Turing Machines
- Computational Work and Time on Finite Machines
- Continuous optimization problems and a polynomial hierarchy of real functions
- Enumerative counting is hard
- scientific article; zbMATH DE number 3814972 (Why is no real title available?)
- scientific article; zbMATH DE number 3921977 (Why is no real title available?)
- scientific article; zbMATH DE number 4033108 (Why is no real title available?)
- scientific article; zbMATH DE number 4074483 (Why is no real title available?)
- scientific article; zbMATH DE number 15884 (Why is no real title available?)
- scientific article; zbMATH DE number 17806 (Why is no real title available?)
- scientific article; zbMATH DE number 3596249 (Why is no real title available?)
- scientific article; zbMATH DE number 3597592 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- NP is as easy as detecting unique solutions
- On Approximation Algorithms for # P
- On counting problems and the polynomial-time hierarchy
- On sparse oracles separating feasible complexity classes
- P-Printable Sets
- Random generation of combinatorial structures from a uniform distribution
- Relativized Polynomial Time Hierarchies Having Exactly K Levels
- Sets with small generalized Kolmogorov complexity
- Some consequences of non-uniform conditions on uniform classes
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- The complexity of computing the permanent
- The Complexity of Enumeration and Reliability Problems
- The complexity of theorem-proving procedures
- The polynomial-time hierarchy
Cited in
(22)- 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
- On the minimax decision rules in ranking problems
- Characterizing the existence of one-way permutations
- Recursion-theoretic ranking and compression
- Tally NP sets and easy census functions.
- Optimal series-parallel trade-offs for reducing a function to its own graph
- On the hardness of maximum rank aggregation problems
- Closure and nonclosure properties of the classes of compressible and rankable sets
- An Arrovian impossibility in combining ranking and evaluation
- The enumerability of P collapses P to NC
- All superlinear inverse schemes are coNP-hard
- A Survey of Ranking Theory
- CONSTRUCTING LANGUAGE INSTANCES BASED ON PARTIAL INFORMATION
- Ranking Sets of Objects: The Complexity of Avoiding Impossibility Results
- A Survey of Ranking Theory
- Ranking with a P-Norm Push
- Automata, Languages and Programming
- On weakly and strongly popular rankings
This page was built for publication: On the complexity of ranking
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q920620)
