Reference:

Christoph Haase and Stefan Kiefer. The complexity of the th largest subset problem and related problems. Information Processing Letters (IPL), 116(2):111–115, 2016.

Abstract:

We show that the th largest subset problem and the th largest -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.

Suggested BibTeX entry:

@article{16HK-IPL,
    author = {Christoph Haase and Stefan Kiefer},
    journal = {Information Processing Letters (IPL)},
    number = {2},
    pages = {111--115},
    publisher = {Elsevier},
    title = {The complexity of the ${K}$th largest subset problem and related problems},
    volume = {116},
    year = {2016}
}