The complexity of the Kth largest subset problem and related problems

DOI10.1016/J.IPL.2015.09.015zbMATH Open1346.68110arXiv1501.06729OpenAlexW2167091017MaRDI QIDQ894449FDOQ894449

Authors: Christoph Haase, Stefan Kiefer 

Publication date: 1 December 2015

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

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.

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

Recommendations

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• 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)