The complexity of the Kth largest subset problem and related problems

DOI10.1016/J.IPL.2015.09.015MaRDI QIDQ894449zbMATH OpenOpenAlexFDO

Authors 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)

Abstract: We show that the Kth largest subset problem and the Kth largest m-tuple problem are in PP and hard for PP under polynomial-time Turing reductions. Several problems from the literature were previously shown NP-hard via reductions from those two problems, and by our main result they become PP-hard as well. We also provide complementary PP-upper bounds for some of them.

Recommendations

• scientific article; zbMATH DE number 140473
• On the complexity of the maximum subgraph problem
• scientific article; zbMATH DE number 1506074
• PP is as Hard as the Polynomial-Time Hierarchy
• scientific article; zbMATH DE number 18529

Cites work

• scientific article; zbMATH DE number 140473 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• Computability and complexity theory.
• Computational Complexity of Probabilistic Turing Machines
• Foundations of Software Science and Computational Structures
• Lower Bounds for Selection in X + Y and Other Multisets
• PP is as Hard as the Polynomial-Time Hierarchy
• Selecting the Kth Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $
• The Complexity of Planar Counting Problems
• The Complexity of Vertex Enumeration Methods
• The complexity of power-index comparison

Cited in

(7)

• Probabilistic causes in Markov chains
• Further results on an abstract model for branching and its application to mixed integer programming
• Percentile queries in multi-dimensional Markov decision processes
• On computing small variable disjunction branch-and-bound trees
• The odds of staying on budget
• scientific article; zbMATH DE number 7561341 (Why is no real title available?)
• Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games

This page was built for publication: The complexity of the \(K\)th largest subset problem and related problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q894449)