The complexity of the \(K\)th largest subset problem and related problems

DOI10.1016/j.ipl.2015.09.015zbMath1346.68110arXiv1501.06729OpenAlexW2167091017MaRDI QIDQ894449

Christoph Haase, Stefan Kiefer

Publication date: 1 December 2015

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1501.06729

zbMATH Keywords

PPcomputational complexitycounting problems\(K\)th largest \(m\)-tuple\(K\)th largest subset

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

The Odds of Staying on Budget, Probabilistic causes in Markov chains, Percentile queries in multi-dimensional Markov decision processes, Further results on an abstract model for branching and its application to mixed integer programming, Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computability and complexity theory.
• The complexity of power-index comparison
• The Complexity of Vertex Enumeration Methods
• PP is as Hard as the Polynomial-Time Hierarchy
• Computational Complexity of Probabilistic Turing Machines
• Selecting the Kth Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $
• Lower Bounds for Selection in X + Y and Other Multisets
• The Complexity of Planar Counting Problems
• Foundations of Software Science and Computational Structures