Article ID Journal Published Year Pages File Type
10331032 Information Processing Letters 2016 5 Pages PDF
Abstract
We show that the Kth largest subset problem and the Kth largestm-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.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
The complexity of the Kth largest subset problem and related problems
Authors
, ,